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
|
package dotty.tools.backend.jvm
import dotty.tools.dotc.ast.tpd
import dotty.tools.dotc.core.Contexts.Context
import dotty.tools.dotc.core.Types
import dotty.tools.dotc.transform.TreeTransforms.{TransformerInfo, TreeTransform, MiniPhase, MiniPhaseTransform}
import dotty.tools.dotc.ast.tpd
import dotty.tools.dotc
import dotty.tools.dotc.backend.jvm.DottyPrimitives
import dotty.tools.dotc.core.Flags.FlagSet
import dotty.tools.dotc.transform.Erasure
import dotty.tools.dotc.transform.SymUtils._
import java.io.{File => JFile}
import scala.collection.generic.Clearable
import scala.collection.mutable
import scala.collection.mutable.{ListBuffer, ArrayBuffer}
import scala.reflect.ClassTag
import scala.reflect.internal.util.WeakHashSet
import scala.reflect.io.{Directory, PlainDirectory, AbstractFile}
import scala.tools.asm.{ClassVisitor, FieldVisitor, MethodVisitor}
import scala.tools.nsc.backend.jvm.{BCodeHelpers, BackendInterface}
import dotty.tools.dotc.core._
import Periods._
import SymDenotations._
import Contexts._
import Types._
import Symbols._
import Denotations._
import Phases._
import java.lang.AssertionError
import dotty.tools.dotc.util.Positions.Position
import Decorators._
import tpd._
import Flags._
import StdNames.nme
/**
* Verifies that each Label DefDef has only a single address to jump back and
* reorders them such that they are not nested and this address is a fall-through address for JVM
*
* ei such code
*
*
* <label> def foo(i: Int) = {
* <label> def bar = 0
* <label> def dough(i: Int) = if(i == 0) bar else foo(i-1)
* dough(i)
* }
*
* foo(100)
*
* will get rewritten to
*
* \
* <label> def foo(i: Int) = dough(i)
* <label> def dough(i: Int) = if(i == 0) bar else foo(i-1)
* <label> def bar = 2
* foo(100)
*
* Proposed way to generate this pattern in backend is:
*
* foo(100)
* <jump foo>
* <label> def foo(i: Int) = dough(i)
* // <jump a> // unreachable
* <label> def dough(i: Int) = if(i == 0) bar else foo(i-1)
* // <jump a> // unreachable
* <label> def bar = 2
* // <jump a> // unreachable
* <asm point a>
*
* Unreachable jumps will be eliminated by local dead code analysis.
* After JVM is smart enough to remove next-line jumps
*
* Note that Label DefDefs can be only nested in Block, otherwise no one would be able to call them
* Other DefDefs are eliminated
*/
class LabelDefs extends MiniPhaseTransform {
def phaseName: String = "labelDef"
val queue = new ArrayBuffer[Tree]()
override def transformDefDef(tree: tpd.DefDef)(implicit ctx: Context, info: TransformerInfo): tpd.Tree = {
if (tree.symbol is Flags.Label) tree
else {
collectLabelDefs.clear
val newRhs = collectLabelDefs.transform(tree.rhs)
val labelCalls = collectLabelDefs.labelCalls
var entryPoints = collectLabelDefs.parentLabelCalls
var labelDefs = collectLabelDefs.labelDefs
// make sure that for every label there's a single location it should return and single entry point
// if theres already a location that it returns to that's a failure
val disallowed = new mutable.HashMap[Symbol, Tree]()
queue.sizeHint(labelCalls.size + entryPoints.size)
def moveLabels(entryPoint: Tree): List[Tree] = {
if ((entryPoint.symbol is Flags.Label) && labelDefs.contains(entryPoint.symbol)) {
val visitedNow = new mutable.HashMap[Symbol, Tree]()
val treesToAppend = new ArrayBuffer[Tree]() // order matters. parents should go first
queue.clear()
var visited = 0
queue += entryPoint
while (visited < queue.size) {
val owningLabelDefSym = queue(visited).symbol
val owningLabelDef = labelDefs(owningLabelDefSym)
for (call <- labelCalls(owningLabelDefSym))
if (disallowed.contains(call.symbol)) {
val oldCall = disallowed(call.symbol)
ctx.error(s"Multiple return locations for Label $oldCall and $call", call.symbol.pos)
} else {
if ((!visitedNow.contains(call.symbol)) && labelDefs.contains(call.symbol)) {
visitedNow.put(call.symbol, labelDefs(call.symbol))
queue += call
}
}
if (!treesToAppend.contains(owningLabelDef)) {
treesToAppend += owningLabelDef
}
visited += 1
}
disallowed ++= visitedNow
treesToAppend.toList
} else Nil
}
val putLabelDefsNearCallees = new TreeMap() {
override def transform(tree: tpd.Tree)(implicit ctx: Context): tpd.Tree = {
tree match {
case t: Apply if (entryPoints.contains(t)) =>
entryPoints = entryPoints - t
Block(moveLabels(t), t)
case _ => if (entryPoints.nonEmpty && labelDefs.nonEmpty) super.transform(tree) else tree
}
}
}
val res = cpy.DefDef(tree)(rhs = putLabelDefsNearCallees.transform(newRhs))
res
}
}
val collectLabelDefs = new TreeMap() {
// label calls from this DefDef
var parentLabelCalls: mutable.Set[Tree] = new mutable.HashSet[Tree]()
var isInsideLabel = false
var isInsideBlock = false
def shouldMoveLabel = true
// labelSymbol -> Defining tree
val labelDefs = new mutable.HashMap[Symbol, Tree]()
// owner -> all calls by this owner
val labelCalls = new mutable.HashMap[Symbol, mutable.Set[Tree]]()
def clear = {
parentLabelCalls.clear()
labelDefs.clear()
labelCalls.clear()
}
override def transform(tree: tpd.Tree)(implicit ctx: Context): tpd.Tree = tree match {
case t: Template => t
case t: Block =>
val tmp = isInsideBlock
isInsideBlock = true
val r = super.transform(t)
isInsideBlock = tmp
r
case t: DefDef =>
assert(t.symbol is Flags.Label)
val st = parentLabelCalls
parentLabelCalls = new mutable.HashSet[Tree]()
val tmp = isInsideLabel
isInsideLabel = true
val r = super.transform(tree)
isInsideLabel = tmp
labelCalls(r.symbol) = parentLabelCalls
parentLabelCalls = st
if(shouldMoveLabel) {
labelDefs(r.symbol) = r
EmptyTree
} else r
case t: Apply if t.symbol is Flags.Label =>
parentLabelCalls = parentLabelCalls + t
super.transform(tree)
case _ =>
super.transform(tree)
}
}
}
|
