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
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
|
/* NSC -- new scala compiler
* Copyright 2005-2009 LAMP/EPFL
* @author Iulian Dragos
*/
// $Id$
package scala.tools.nsc
package transform
import scala.tools.nsc.symtab.Flags
/** Perform tail recursive call elimination.
*
* @author Iulian Dragos
* @version 1.0
*/
abstract class TailCalls extends Transform
/* with JavaLogging() */ {
// inherits abstract value `global' and class `Phase' from Transform
import global._ // the global environment
import definitions._ // standard classes and methods
import typer.{typed, atOwner} // methods to type trees
val phaseName: String = "tailcalls"
def newTransformer(unit: CompilationUnit): Transformer =
new TailCallElimination(unit)
/** Create a new phase which applies transformer */
override def newPhase(prev: scala.tools.nsc.Phase): StdPhase = new Phase(prev)
/** The phase defined by this transform */
class Phase(prev: scala.tools.nsc.Phase) extends StdPhase(prev) {
def apply(unit: global.CompilationUnit) {
if (!(settings.debuginfo.value == "notailcalls")) {
newTransformer(unit).transformUnit(unit);
}
}
}
/** The @tailrec annotation indicates TCO is mandatory */
private def tailrecRequired(defdef: DefDef) = defdef.symbol hasAnnotation TailrecClass
/**
* A Tail Call Transformer
*
* @author Erik Stenman, Iulian Dragos
* @version 1.1
*
* What it does:
* <p>
* Finds method calls in tail-position and replaces them with jumps.
* A call is in a tail-position if it is the last instruction to be
* executed in the body of a method. This is done by recursing over
* the trees that may contain calls in tail-position (trees that can't
* contain such calls are not transformed). However, they are not that
* many.
* </p>
* <p>
* Self-recursive calls in tail-position are replaced by jumps to a
* label at the beginning of the method. As the JVM provides no way to
* jump from a method to another one, non-recursive calls in
* tail-position are not optimized.
* </p>
* <p>
* A method call is self-recursive if it calls the current method and
* the method is final (otherwise, it could
* be a call to an overridden method in a subclass). Furthermore, If
* the method has type parameters, the call must contain these
* parameters as type arguments. Recursive calls on a different instance
* are optimized. Since 'this' is not a local variable, a dummy local val
* is added and used as a label parameter. The backend knows to load
* the corresponding argument in the 'this' (local at index 0). This dummy local
* is never used and should be cleand up by dead code elmination (when enabled).
* </p>
* <p>
* This phase has been moved before pattern matching to catch more
* of the common cases of tail recursive functions. This means that
* more cases should be taken into account (like nested function, and
* pattern cases).
* </p>
* <p>
* If a method contains self-recursive calls, a label is added to at
* the beginning of its body and the calls are replaced by jumps to
* that label.
* </p>
* <p>
* Assumes: <code>Uncurry</code> has been run already, and no multiple
* parameter lists exit.
* </p>
*/
class TailCallElimination(unit: CompilationUnit) extends Transformer {
class Context {
/** The current method */
var currentMethod: Symbol = NoSymbol
/** The current tail-call label */
var label: Symbol = NoSymbol
/** The expected type arguments of self-recursive calls */
var tparams: List[Symbol] = Nil
/** Tells whether we are in a (possible) tail position */
var tailPos = false
/** Is the label accessed? */
var accessed = false
def this(that: Context) = {
this()
this.currentMethod = that.currentMethod
this.label = that.label
this.tparams = that.tparams
this.tailPos = that.tailPos
this.accessed = that.accessed
}
/** Create a new method symbol for the current method and store it in
* the label field.
*/
def makeLabel(): Unit = {
label = currentMethod.newLabel(currentMethod.pos, "_" + currentMethod.name)
accessed = false
}
override def toString(): String = (
"" + currentMethod.name + " tparams: " + tparams + " tailPos: " + tailPos +
" accessed: " + accessed + "\nLabel: " + label + "\nLabel type: " + label.info
)
}
private def mkContext(that: Context) = new Context(that)
private def mkContext(that: Context, tp: Boolean): Context = {
val t = mkContext(that)
t.tailPos = tp
t
}
private var ctx: Context = new Context()
/** Rewrite this tree to contain no tail recursive calls */
def transform(tree: Tree, nctx: Context): Tree = {
val oldCtx = ctx
ctx = nctx
val t = transform(tree)
this.ctx = oldCtx
t
}
override def transform(tree: Tree): Tree = {
tree match {
case dd @ DefDef(mods, name, tparams, vparams, tpt, rhs) =>
log("Entering DefDef: " + name)
var isTransformed = false
val newCtx = mkContext(ctx)
newCtx.currentMethod = tree.symbol
newCtx.makeLabel()
val currentClassParam = tree.symbol.newSyntheticValueParam(currentClass.tpe)
newCtx.label.setInfo(MethodType(currentClassParam :: tree.symbol.tpe.params, tree.symbol.tpe.finalResultType))
newCtx.tailPos = true
val t1 = if (newCtx.currentMethod.isFinal ||
newCtx.currentMethod.enclClass.hasFlag(Flags.MODULE)) {
newCtx.tparams = Nil
log(" Considering " + name + " for tailcalls")
tree.symbol.tpe match {
case PolyType(tpes, restpe) =>
newCtx.tparams = tparams map (_.symbol)
newCtx.label.setInfo(
newCtx.label.tpe.substSym(tpes, tparams map (_.symbol)))
case _ => ()
}
//println("label.tpe: " + newCtx.label.tpe)
var newRHS = transform(rhs, newCtx);
if (newCtx.accessed) {
log("Rewrote def " + newCtx.currentMethod)
isTransformed = true
val newThis = newCtx.currentMethod.newValue(tree.pos, nme.THIS)
.setInfo(currentClass.tpe)
.setFlag(Flags.SYNTHETIC)
newRHS =
typed(atPos(tree.pos)(Block(List(
ValDef(newThis, This(currentClass))),
LabelDef(newCtx.label,
newThis :: (List.flatten(vparams) map (_.symbol)),
newRHS))));
treeCopy.DefDef(tree, mods, name, tparams, vparams, tpt, newRHS);
} else
treeCopy.DefDef(tree, mods, name, tparams, vparams, tpt, newRHS);
} else {
treeCopy.DefDef(tree, mods, name, tparams, vparams, tpt, transform(rhs, newCtx))
}
if (!isTransformed && tailrecRequired(dd))
unit.error(dd.pos, "could not optimize @tailrec annotated method")
log("Leaving DefDef: " + name)
t1
case EmptyTree => tree
case PackageDef(_, _) =>
super.transform(tree)
case ClassDef(_, name, _, _) =>
log("Entering class " + name)
val res = super.transform(tree)
log("Leaving class " + name)
res
case ValDef(mods, name, tpt, rhs) => super.transform(tree)
case LabelDef(name, params, rhs) => super.transform(tree)
case Template(parents, self, body) =>
super.transform(tree)
case Block(stats, expr) =>
treeCopy.Block(tree,
transformTrees(stats, mkContext(ctx, false)),
transform(expr))
case CaseDef(pat, guard, body) =>
treeCopy.CaseDef(tree, pat, guard, transform(body))
case Sequence(_) | Alternative(_) |
Star(_) | Bind(_, _) =>
throw new RuntimeException("We should've never gotten inside a pattern")
case Function(vparams, body) =>
tree
//throw new RuntimeException("Anonymous function should not exist at this point. at: " + unit.position(tree.pos));
case Assign(lhs, rhs) =>
super.transform(tree)
case If(cond, thenp, elsep) =>
treeCopy.If(tree, cond, transform(thenp), transform(elsep))
case Match(selector, cases) => //super.transform(tree);
treeCopy.Match(tree, transform(selector, mkContext(ctx, false)), transformTrees(cases).asInstanceOf[List[CaseDef]])
case Return(expr) => super.transform(tree)
case Try(block, catches, finalizer) =>
// no calls inside a try are in tail position, but keep recursing for nested functions
treeCopy.Try(tree, transform(block, mkContext(ctx, false)),
transformTrees(catches, mkContext(ctx, false)).asInstanceOf[List[CaseDef]],
transform(finalizer, mkContext(ctx, false)))
case Throw(expr) => super.transform(tree)
case New(tpt) => super.transform(tree)
case Typed(expr, tpt) => super.transform(tree)
case Apply(tapply @ TypeApply(fun, targs), vargs) =>
lazy val defaultTree = treeCopy.Apply(tree, tapply, transformTrees(vargs, mkContext(ctx, false)))
if ( ctx.currentMethod.isFinal &&
ctx.tailPos &&
isSameTypes(ctx.tparams, targs map (_.tpe.typeSymbol)) &&
isRecursiveCall(fun)) {
fun match {
case Select(receiver, _) =>
val recTpe = receiver.tpe.widen
val enclTpe = ctx.currentMethod.enclClass.typeOfThis
// make sure the type of 'this' doesn't change through this polymorphic recursive call
if (!forMSIL &&
(receiver.tpe.typeParams.isEmpty ||
(receiver.tpe.widen == ctx.currentMethod.enclClass.typeOfThis)))
rewriteTailCall(fun, receiver :: transformTrees(vargs, mkContext(ctx, false)))
else
defaultTree
case _ => rewriteTailCall(fun, This(currentClass) :: transformTrees(vargs, mkContext(ctx, false)))
}
} else
defaultTree
case TypeApply(fun, args) =>
super.transform(tree)
case Apply(fun, args) if (fun.symbol == definitions.Boolean_or ||
fun.symbol == definitions.Boolean_and) =>
treeCopy.Apply(tree, fun, transformTrees(args))
case Apply(fun, args) =>
lazy val defaultTree = treeCopy.Apply(tree, fun, transformTrees(args, mkContext(ctx, false)))
if (ctx.currentMethod.isFinal &&
ctx.tailPos &&
isRecursiveCall(fun)) {
fun match {
case Select(receiver, _) =>
if (!forMSIL)
rewriteTailCall(fun, receiver :: transformTrees(args, mkContext(ctx, false)))
else
defaultTree
case _ => rewriteTailCall(fun, This(currentClass) :: transformTrees(args, mkContext(ctx, false)))
}
} else
defaultTree
case Super(qual, mix) =>
tree
case This(qual) =>
tree
case Select(qualifier, selector) =>
tree
case Ident(name) =>
tree
case Literal(value) =>
tree
case TypeTree() =>
tree
case _ =>
tree
}
}
def transformTrees(trees: List[Tree], nctx: Context): List[Tree] =
trees map ((tree) => transform(tree, nctx))
private def rewriteTailCall(fun: Tree, args: List[Tree]): Tree = {
log("Rewriting tail recursive method call at: " +
(fun.pos))
ctx.accessed = true
//println("fun: " + fun + " args: " + args)
val t = atPos(fun.pos)(Apply(Ident(ctx.label), args))
// println("TAIL: "+t)
typed(t)
}
private def isSameTypes(ts1: List[Symbol], ts2: List[Symbol]): Boolean = {
def isSameType(t1: Symbol, t2: Symbol) = {
t1 == t2
}
List.forall2(ts1, ts2)(isSameType)
}
/** Returns <code>true</code> if the fun tree refers to the same method as
* the one saved in <code>ctx</code>.
*
* @param fun the expression that is applied
* @return <code>true</code> if the tree symbol refers to the innermost
* enclosing method
*/
private def isRecursiveCall(fun: Tree): Boolean =
(fun.symbol eq ctx.currentMethod)
}
}
|