FindTailCalls


1   package gnu.expr;
2   import gnu.bytecode.Type;
3   
4   /** Does setTailCall on ApplyExp's that are tail-calls.
5       Also setCanRead, setCanCall, setCanWrite on Declarations
6       and setCanRead, setCanCall on LambdaExp when appropriate. */
7   
8   public class FindTailCalls extends ExpWalker
9   {
10    public static void findTailCalls (Expression exp, Compilation comp)
11    {
12      FindTailCalls walker = new FindTailCalls();
13      walker.setContext(comp);
14      walker.walk(exp);
15    }
16  
17    boolean inTailContext = true;
18  
19    protected Expression walkApplyExp(ApplyExp exp)
20    {
21      if (inTailContext)
22        exp.setTailCall(true);
23      exp.context = currentLambda;
24      boolean save = inTailContext;
25      LambdaExp lexp = null;
26      try
27        {
28      inTailContext = false;
29      boolean isAppendValues = false;
30      if (exp.func instanceof ReferenceExp)
31        {
32          ReferenceExp func = (ReferenceExp) exp.func;
33          Declaration binding = Declaration.followAliases(func.binding);
34          if (binding != null)
35            {
36                  // No point in building chain if STATIC_SPECIFIED, and it can
37                  // lead to memory leaks.  At least if interactive calls cam
38                  // resolve to previously-compiled Declarations (as in XQuery).
39                  if (! binding.getFlag(Declaration.STATIC_SPECIFIED))
40                    {
41                      exp.nextCall = binding.firstCall;
42                      binding.firstCall = exp;
43                    }
44                  Compilation comp = getCompilation();
45          binding.setCanCall();
46                  if (! comp.mustCompile)
47                    // Avoid tricky optimization if we're interpreting.
48                    binding.setCanRead();
49          Expression value = binding.getValue();
50          if (value instanceof LambdaExp)
51            lexp = (LambdaExp) value;
52            }
53        }
54      else if (exp.func instanceof LambdaExp
55           && ! (exp.func instanceof ClassExp))
56        {
57          lexp = (LambdaExp) exp.func;
58          walkLambdaExp(lexp, false);
59          lexp.setCanCall(true);
60        }
61      else if (exp.func instanceof QuoteExp
62           && (((QuoteExp) exp.func).getValue()
63               == gnu.kawa.functions.AppendValues.appendValues))
64        isAppendValues = true;
65      else
66        exp.func = (Expression) exp.func.walk(this);
67      if (lexp != null)
68        {
69          if (lexp.returnContinuation == exp) ; // OK
70          else if (lexp == currentLambda && save)
71            ; // (Self-)tail-recursion is OK.
72          else if (lexp.returnContinuation == null)
73            lexp.returnContinuation = exp;
74          else
75            lexp.returnContinuation = LambdaExp.unknownContinuation;
76        }
77      if (isAppendValues && exp.args.length > 0)
78        {
79          int last = exp.args.length - 1;
80          exp.args = walkExps(exp.args, last);
81          inTailContext = save;
82          exp.args[last] = walk(exp.args[last]);
83        }
84      else
85        exp.args = walkExps(exp.args);
86      return exp;
87        }
88      finally
89        {
90      inTailContext = save;
91        }
92    }
93  
94    protected Expression walkBeginExp(BeginExp exp)
95    {
96      boolean save = inTailContext;
97      try
98        {
99      int n = exp.length - 1;
100     for (int i = 0;  i <= n;  i++)
101       {
102         inTailContext = (i == n) && save;
103         exp.exps[i] = (Expression) exp.exps[i].walk(this);
104       }
105     return exp;
106       }
107     finally
108       {
109     inTailContext = save;
110       }
111   }
112 
113   protected Expression walkFluidLetExp (FluidLetExp exp)
114   {
115     for (Declaration decl = exp.firstDecl();
116          decl != null; decl = decl.nextDecl())
117       {
118         decl.setCanRead(true);
119         decl.setCanWrite(true);
120         if (decl.base != null)
121           {
122             decl.base.setCanRead(true);
123             decl.base.setCanWrite(true);
124           }
125       }
126     boolean save = inTailContext;
127     inTailContext = false;
128     try
129       {
130     return super.walkFluidLetExp(exp);
131       }
132     finally
133       {
134     inTailContext = save;
135       }
136   }
137 
138   protected Expression walkLetExp (LetExp exp)
139   {
140     int n = exp.inits.length; 
141     boolean save = inTailContext;
142     Declaration decl;
143     try
144       {
145     inTailContext = false;
146 
147     decl = exp.firstDecl();
148     for (int i = 0;  i < n;  i++, decl = decl.nextDecl())
149       {
150         Expression init = walkSetExp (decl, exp.inits[i]);
151         // Optimize letrec-like forms.
152         if (init == QuoteExp.undefined_exp)
153           {
154         Expression value = decl.getValue();
155         if (value instanceof LambdaExp
156             || (value != init && value instanceof QuoteExp))
157           init = value;
158           }
159         exp.inits[i] = init;
160       }
161       }
162     finally
163       {
164     inTailContext = save;
165       }
166     exp.body = (Expression) exp.body.walk(this);
167     walkDecls(exp);
168     return exp;
169   }
170 
171   public void walkDecls (ScopeExp exp)
172   {
173     Declaration decl = exp.firstDecl();
174     for (;  decl != null;  decl = decl.nextDecl())
175       {
176     Expression value = decl.getValue();
177     if (value instanceof LambdaExp)
178       {
179         LambdaExp lexp = (LambdaExp) value;
180         if (decl.getCanRead())
181           lexp.setCanRead(true);
182         if (decl.getCanCall())
183           lexp.setCanCall(true);
184       }
185         if (decl.getFlag(Declaration.EXPORT_SPECIFIED)
186             && value instanceof ReferenceExp)
187           {
188             ReferenceExp rexp = (ReferenceExp) value;
189             Declaration context = rexp.contextDecl();
190             if (context != null && context.isPrivate())
191               context.setFlag(Declaration.EXTERNAL_ACCESS);
192           }
193       }
194   }
195 
196   protected Expression walkIfExp (IfExp exp)
197   {
198     boolean save = inTailContext;
199     try
200       {
201     inTailContext = false;
202     exp.test = (Expression) exp.test.walk(this);
203       }
204     finally
205       {
206     inTailContext = save;
207       }
208     exp.then_clause = (Expression) exp.then_clause.walk(this);
209     Expression else_clause = exp.else_clause;
210     if (else_clause != null)
211       exp.else_clause = (Expression) else_clause.walk(this);
212     return exp;
213   }
214 
215   protected Expression walkLambdaExp (LambdaExp exp)
216   {
217     walkLambdaExp (exp, true);
218     return exp;
219   }
220 
221   final void walkLambdaExp (LambdaExp exp, boolean canRead)
222   {
223     boolean save = inTailContext;
224     LambdaExp parent = currentLambda;
225     currentLambda = exp;
226     if (canRead)
227       exp.setCanRead(true);
228     try
229       {
230     inTailContext = false;
231     if (exp.defaultArgs != null)
232       exp.defaultArgs = walkExps(exp.defaultArgs);
233     inTailContext = exp.getInlineOnly() ? save : true;
234     if (exitValue == null && exp.body != null)
235       exp.body = (Expression) exp.body.walk(this);
236       }
237     finally
238       {
239     inTailContext = save;
240     currentLambda = parent;
241       }
242 
243     walkDecls(exp);
244 
245     for (LambdaExp child = exp.firstChild;  child != null;
246      child = child.nextSibling)
247       {
248     if (child.getCanRead()
249         || child.isClassMethod()
250         || child.min_args != child.max_args)
251       child.flags |= LambdaExp.CANNOT_INLINE;
252     else
253       {
254         ApplyExp caller = child.returnContinuation;
255         if (caller != LambdaExp.unknownContinuation
256         && ! comp.usingCPStyle())
257           {
258         child.setInlineOnly(true);
259           }
260       }
261       }
262 
263     for (LambdaExp child = exp.firstChild;  child != null;
264      child = child.nextSibling)
265       {
266     if ((child.flags & (LambdaExp.CANNOT_INLINE|LambdaExp.INLINE_ONLY))!=0)
267       continue;
268     // We can inline child if it is a member of a set of functions
269     // which can all be inlined in the same method, and for which
270     // all callers are known and members of the same set,
271     // and each function has at most one caller that is not a tail-call.
272     // FIXME  Basic algorithm:
273     /*
274     Vector inlineSet = new Vector();  // empty
275     ApplyExp[] apl = (ApplyExp[]) applications.get(child);
276     Stack queue = new Stack();
277     copy elements of apl to queue;
278     while (!queue.empty())
279       {
280         LambdaExp caller = (LambdaExp) queue.pop();
281         if ((caller.flags & LambdaExp.CANNOT_INLINE) != 0)
282           {
283         child.flags |= LambdaExp.CANNOT_INLINE;
284         break;
285           }
286         if (caller in inlineSet)
287           continue;
288         apl = (ApplyExp[]) applications.get(child);
289         add elements of apl to queue;
290         add caller to inlineSet;
291         add caller.returnContinuation.context to inlineSet;
292       }
293     */
294       }
295   }
296 
297   // Map LambdaExp to ApplyExp[], which is the set of non-self tails
298   // calls that call the key.
299   // Hashtable applications = new Hashtable();
300 
301   protected Expression walkClassExp (ClassExp exp)
302   {
303     boolean save = inTailContext;
304     LambdaExp parent = currentLambda;
305     currentLambda = exp;
306     exp.setCanRead(true);
307     try
308       {
309     inTailContext = false;
310     for (LambdaExp child = exp.firstChild;
311          child != null && exitValue == null;  child = child.nextSibling)
312       walkLambdaExp(child, false);
313       }
314     finally
315       {
316     inTailContext = save;
317     currentLambda = parent;
318       }
319 
320     return exp;
321   }
322 
323   protected Expression walkReferenceExp (ReferenceExp exp)
324   {
325     Declaration decl = Declaration.followAliases(exp.binding);
326     if (decl != null)
327       {
328         // Replace references to a void variable (including one whose value
329         // is the empty sequence in XQuery) by an empty constant.  This is
330         // not so much an optimization as avoiding the complications and
331         // paradoxes of variables and expression that are void.
332         if (decl.type == Type.void_type)
333           return QuoteExp.voidExp;
334         decl.setCanRead(true);
335       }
336     Declaration ctx = exp.contextDecl();
337     if (ctx != null)
338       ctx.setCanRead(true);
339     return exp;
340   }
341 
342   final Expression walkSetExp (Declaration decl, Expression value)
343   {
344     if (decl != null && decl.getValue() == value
345     && value instanceof LambdaExp && ! (value instanceof ClassExp)
346         && ! decl.isPublic())
347       {
348     LambdaExp lexp = (LambdaExp) value; 
349     walkLambdaExp(lexp, false);
350     return lexp;
351       }
352     else
353       return (Expression) value.walk(this);
354   }
355 
356   protected Expression walkSetExp (SetExp exp)
357   {
358     boolean save = inTailContext;
359     try
360       {
361     inTailContext = false;
362     Declaration decl = exp.binding;
363     if (decl != null && decl.isAlias())
364       {
365         if (exp.isDefining())
366           {
367         exp.new_value = (Expression) exp.new_value.walk(this);
368         return exp;
369           }
370         decl = Declaration.followAliases(decl);
371       }
372     if (decl != null)
373       decl.setCanWrite();
374         Declaration ctx = exp.contextDecl();
375         if (ctx != null)
376           ctx.setCanRead(true);
377     Expression value = walkSetExp(decl, exp.new_value);
378     if (decl != null && decl.context instanceof LetExp
379         && value == decl.getValue()
380         && (value instanceof LambdaExp || value instanceof QuoteExp))
381       {
382         // The assignment is redundant, as it has been moved to the
383         // initialization of the LetExp.
384         return QuoteExp.voidExp;
385       }
386     exp.new_value = value;
387     return exp;
388       }
389     finally
390       {
391     inTailContext = save;
392       }
393   }
394 
395   protected Expression walkTryExp (TryExp exp)
396   {
397     boolean save = inTailContext;
398     try
399       {
400     inTailContext = false;
401     return super.walkTryExp(exp);
402       }
403     finally
404       {
405     inTailContext = save;
406       }
407   }
408 
409   protected Expression walkSynchronizedExp (SynchronizedExp exp)
410   {
411     boolean save = inTailContext;
412     try
413       {
414     inTailContext = false;
415     return super.walkSynchronizedExp(exp);
416       }
417     finally
418       {
419     inTailContext = save;
420       }
421   }
422 }
423
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags