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
|
/* NSC -- new scala compiler
* Copyright 2005-2011 LAMP/EPFL
* @author Iulian Dragos
*/
package scala.tools.nsc
package transform
import symtab.Flags
import Flags.SYNTHETIC
/** Perform tail recursive call elimination.
*
* @author Iulian Dragos
* @version 1.0
*/
abstract class TailCalls extends Transform {
import global._ // the global environment
import definitions._ // standard classes and methods
import typer.{ typed, typedPos } // 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);
}
}
}
/**
* 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 elimination (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 {
private val defaultReason = "it contains a recursive call not in tail position"
class Context() {
/** The current method */
var method: 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
/** The reason this method could not be optimized. */
var failReason = defaultReason
var failPos = method.pos
/** Has the label been accessed? */
var accessed = false
def this(that: Context) = {
this()
this.method = that.method
this.tparams = that.tparams
this.tailPos = that.tailPos
this.accessed = that.accessed
this.failPos = that.failPos
this.label = that.label
}
def this(dd: DefDef) {
this()
this.method = dd.symbol
this.tparams = dd.tparams map (_.symbol)
this.tailPos = true
this.accessed = false
this.failPos = dd.pos
/** Create a new method symbol for the current method and store it in
* the label field.
*/
this.label = {
val label = method.newLabel(method.pos, "_" + method.name)
val thisParam = method.newSyntheticValueParam(currentClass.typeOfThis)
label setInfo MethodType(thisParam :: method.tpe.params, method.tpe.finalResultType)
}
if (isEligible)
label setInfo label.tpe.substSym(method.tpe.typeParams, tparams)
}
def enclosingType = method.enclClass.typeOfThis
def methodTypeParams = method.tpe.typeParams
def isEligible = method.isEffectivelyFinal
// @tailrec annotation indicates mandatory transformation
def isMandatory = method.hasAnnotation(TailrecClass) && !forMSIL
def isTransformed = isEligible && accessed
def tailrecFailure() = unit.error(failPos, "could not optimize @tailrec annotated " + method + ": " + failReason)
def newThis(pos: Position) = method.newValue(pos, nme.THIS) setInfo currentClass.typeOfThis setFlag SYNTHETIC
override def toString(): String = (
"" + method.name + " tparams: " + tparams + " tailPos: " + tailPos +
" accessed: " + accessed + "\nLabel: " + label + "\nLabel type: " + label.info
)
}
private var ctx: Context = new Context()
private def noTailContext() = {
val t = new Context(ctx)
t.tailPos = false
t
}
/** Rewrite this tree to contain no tail recursive calls */
def transform(tree: Tree, nctx: Context): Tree = {
val saved = ctx
ctx = nctx
try transform(tree)
finally this.ctx = saved
}
def noTailTransform(tree: Tree): Tree = transform(tree, noTailContext())
def noTailTransforms(trees: List[Tree]) = {
val nctx = noTailContext()
trees map (t => transform(t, nctx))
}
override def transform(tree: Tree): Tree = {
/** A possibly polymorphic apply to be considered for tail call transformation.
*/
def rewriteApply(target: Tree, fun: Tree, targs: List[Tree], args: List[Tree]) = {
val receiver: Tree = fun match {
case Select(qual, _) => qual
case _ => EmptyTree
}
def receiverIsSame = ctx.enclosingType.widen =:= receiver.tpe.widen
def receiverIsSuper = ctx.enclosingType.widen <:< receiver.tpe.widen
def isRecursiveCall = (ctx.method eq fun.symbol) && ctx.tailPos
def transformArgs = noTailTransforms(args)
def matchesTypeArgs = ctx.tparams sameElements (targs map (_.tpe.typeSymbol))
/** Records failure reason in Context for reporting.
* Position is unchanged (by default, the method definition.)
*/
def fail(reason: String) = {
debuglog("Cannot rewrite recursive call at: " + fun.pos + " because: " + reason)
ctx.failReason = reason
treeCopy.Apply(tree, target, transformArgs)
}
/** Position of failure is that of the tree being considered.
*/
def failHere(reason: String) = {
ctx.failPos = fun.pos
fail(reason)
}
def rewriteTailCall(recv: Tree): Tree = {
log("Rewriting tail recursive call: " + fun.pos.lineContent.trim)
ctx.accessed = true
typedPos(fun.pos)(Apply(Ident(ctx.label), recv :: transformArgs))
}
if (!ctx.isEligible) fail("it is neither private nor final so can be overridden")
else if (!isRecursiveCall) {
if (receiverIsSuper) failHere("it contains a recursive call targetting a supertype")
else failHere(defaultReason)
}
else if (!matchesTypeArgs) failHere("it is called recursively with different type arguments")
else if (receiver == EmptyTree) rewriteTailCall(This(currentClass))
else if (forMSIL) fail("it cannot be optimized on MSIL")
else if (!receiverIsSame) failHere("it changes type of 'this' on a polymorphic recursive call")
else rewriteTailCall(receiver)
}
tree match {
case dd @ DefDef(mods, name, tparams, vparams, tpt, rhs) =>
val newCtx = new Context(dd)
debuglog("Considering " + name + " for tailcalls")
val newRHS = transform(rhs, newCtx)
treeCopy.DefDef(tree, mods, name, tparams, vparams, tpt, {
if (newCtx.isTransformed) {
/** We have rewritten the tree, but there may be nested recursive calls remaining.
* If @tailrec is given we need to fail those now.
*/
if (newCtx.isMandatory) {
for (t @ Apply(fn, _) <- newRHS ; if fn.symbol == newCtx.method) {
newCtx.failPos = t.pos
newCtx.tailrecFailure()
}
}
val newThis = newCtx.newThis(tree.pos)
val vpSyms = vparams.flatten map (_.symbol)
typedPos(tree.pos)(Block(
List(ValDef(newThis, This(currentClass))),
LabelDef(newCtx.label, newThis :: vpSyms, newRHS)
))
}
else {
if (newCtx.isMandatory)
newCtx.tailrecFailure()
newRHS
}
})
case Block(stats, expr) =>
treeCopy.Block(tree,
noTailTransforms(stats),
transform(expr)
)
case CaseDef(pat, guard, body) =>
treeCopy.CaseDef(tree,
pat,
guard,
transform(body)
)
case If(cond, thenp, elsep) =>
treeCopy.If(tree,
cond,
transform(thenp),
transform(elsep)
)
case Match(selector, cases) =>
treeCopy.Match(tree,
noTailTransform(selector),
transformTrees(cases).asInstanceOf[List[CaseDef]]
)
case Try(block, catches, finalizer) =>
// no calls inside a try are in tail position, but keep recursing for nested functions
treeCopy.Try(tree,
noTailTransform(block),
noTailTransforms(catches).asInstanceOf[List[CaseDef]],
noTailTransform(finalizer)
)
case Apply(tapply @ TypeApply(fun, targs), vargs) =>
rewriteApply(tapply, fun, targs, vargs)
case Apply(fun, args) =>
if (fun.symbol == Boolean_or || fun.symbol == Boolean_and)
treeCopy.Apply(tree, fun, transformTrees(args))
else
rewriteApply(fun, fun, Nil, args)
case Alternative(_) | Star(_) | Bind(_, _) =>
sys.error("We should've never gotten inside a pattern")
case EmptyTree | Super(_, _) | This(_) | Select(_, _) | Ident(_) | Literal(_) | Function(_, _) | TypeTree() =>
tree
case _ =>
super.transform(tree)
}
}
}
}
|