001: package gnu.expr;
002:
003: import gnu.bytecode.Type;
004:
005: /** Does setTailCall on ApplyExp's that are tail-calls.
006: Also setCanRead, setCanCall, setCanWrite on Declarations
007: and setCanRead, setCanCall on LambdaExp when appropriate. */
008:
009: public class FindTailCalls extends ExpWalker {
010: public static void findTailCalls(Expression exp, Compilation comp) {
011: FindTailCalls walker = new FindTailCalls();
012: walker.setContext(comp);
013: walker.walk(exp);
014: }
015:
016: boolean inTailContext = true;
017:
018: protected Expression walkApplyExp(ApplyExp exp) {
019: if (inTailContext)
020: exp.setTailCall(true);
021: exp.context = currentLambda;
022: boolean save = inTailContext;
023: LambdaExp lexp = null;
024: try {
025: inTailContext = false;
026: boolean isAppendValues = false;
027: if (exp.func instanceof ReferenceExp) {
028: ReferenceExp func = (ReferenceExp) exp.func;
029: Declaration binding = Declaration
030: .followAliases(func.binding);
031: if (binding != null) {
032: // No point in building chain if STATIC_SPECIFIED, and it can
033: // lead to memory leaks. At least if interactive calls cam
034: // resolve to previously-compiled Declarations (as in XQuery).
035: if (!binding.getFlag(Declaration.STATIC_SPECIFIED)) {
036: exp.nextCall = binding.firstCall;
037: binding.firstCall = exp;
038: }
039: Compilation comp = getCompilation();
040: binding.setCanCall();
041: if (!comp.mustCompile)
042: // Avoid tricky optimization if we're interpreting.
043: binding.setCanRead();
044: Expression value = binding.getValue();
045: if (value instanceof LambdaExp)
046: lexp = (LambdaExp) value;
047: }
048: } else if (exp.func instanceof LambdaExp
049: && !(exp.func instanceof ClassExp)) {
050: lexp = (LambdaExp) exp.func;
051: walkLambdaExp(lexp, false);
052: lexp.setCanCall(true);
053: } else if (exp.func instanceof QuoteExp
054: && (((QuoteExp) exp.func).getValue() == gnu.kawa.functions.AppendValues.appendValues))
055: isAppendValues = true;
056: else
057: exp.func = (Expression) exp.func.walk(this );
058: if (lexp != null) {
059: if (lexp.returnContinuation == exp)
060: ; // OK
061: else if (lexp == currentLambda && save)
062: ; // (Self-)tail-recursion is OK.
063: else if (lexp.returnContinuation == null)
064: lexp.returnContinuation = exp;
065: else
066: lexp.returnContinuation = LambdaExp.unknownContinuation;
067: }
068: if (isAppendValues && exp.args.length > 0) {
069: int last = exp.args.length - 1;
070: exp.args = walkExps(exp.args, last);
071: inTailContext = save;
072: exp.args[last] = walk(exp.args[last]);
073: } else
074: exp.args = walkExps(exp.args);
075: return exp;
076: } finally {
077: inTailContext = save;
078: }
079: }
080:
081: protected Expression walkBeginExp(BeginExp exp) {
082: boolean save = inTailContext;
083: try {
084: int n = exp.length - 1;
085: for (int i = 0; i <= n; i++) {
086: inTailContext = (i == n) && save;
087: exp.exps[i] = (Expression) exp.exps[i].walk(this );
088: }
089: return exp;
090: } finally {
091: inTailContext = save;
092: }
093: }
094:
095: protected Expression walkFluidLetExp(FluidLetExp exp) {
096: for (Declaration decl = exp.firstDecl(); decl != null; decl = decl
097: .nextDecl()) {
098: decl.setCanRead(true);
099: decl.setCanWrite(true);
100: if (decl.base != null) {
101: decl.base.setCanRead(true);
102: decl.base.setCanWrite(true);
103: }
104: }
105: boolean save = inTailContext;
106: inTailContext = false;
107: try {
108: return super .walkFluidLetExp(exp);
109: } finally {
110: inTailContext = save;
111: }
112: }
113:
114: protected Expression walkLetExp(LetExp exp) {
115: int n = exp.inits.length;
116: boolean save = inTailContext;
117: Declaration decl;
118: try {
119: inTailContext = false;
120:
121: decl = exp.firstDecl();
122: for (int i = 0; i < n; i++, decl = decl.nextDecl()) {
123: Expression init = walkSetExp(decl, exp.inits[i]);
124: // Optimize letrec-like forms.
125: if (init == QuoteExp.undefined_exp) {
126: Expression value = decl.getValue();
127: if (value instanceof LambdaExp
128: || (value != init && value instanceof QuoteExp))
129: init = value;
130: }
131: exp.inits[i] = init;
132: }
133: } finally {
134: inTailContext = save;
135: }
136: exp.body = (Expression) exp.body.walk(this );
137: walkDecls(exp);
138: return exp;
139: }
140:
141: public void walkDecls(ScopeExp exp) {
142: Declaration decl = exp.firstDecl();
143: for (; decl != null; decl = decl.nextDecl()) {
144: Expression value = decl.getValue();
145: if (value instanceof LambdaExp) {
146: LambdaExp lexp = (LambdaExp) value;
147: if (decl.getCanRead())
148: lexp.setCanRead(true);
149: if (decl.getCanCall())
150: lexp.setCanCall(true);
151: }
152: if (decl.getFlag(Declaration.EXPORT_SPECIFIED)
153: && value instanceof ReferenceExp) {
154: ReferenceExp rexp = (ReferenceExp) value;
155: Declaration context = rexp.contextDecl();
156: if (context != null && context.isPrivate())
157: context.setFlag(Declaration.EXTERNAL_ACCESS);
158: }
159: }
160: }
161:
162: protected Expression walkIfExp(IfExp exp) {
163: boolean save = inTailContext;
164: try {
165: inTailContext = false;
166: exp.test = (Expression) exp.test.walk(this );
167: } finally {
168: inTailContext = save;
169: }
170: exp.then_clause = (Expression) exp.then_clause.walk(this );
171: Expression else_clause = exp.else_clause;
172: if (else_clause != null)
173: exp.else_clause = (Expression) else_clause.walk(this );
174: return exp;
175: }
176:
177: protected Expression walkLambdaExp(LambdaExp exp) {
178: walkLambdaExp(exp, true);
179: return exp;
180: }
181:
182: final void walkLambdaExp(LambdaExp exp, boolean canRead) {
183: boolean save = inTailContext;
184: LambdaExp parent = currentLambda;
185: currentLambda = exp;
186: if (canRead)
187: exp.setCanRead(true);
188: try {
189: inTailContext = false;
190: if (exp.defaultArgs != null)
191: exp.defaultArgs = walkExps(exp.defaultArgs);
192: inTailContext = exp.getInlineOnly() ? save : true;
193: if (exitValue == null && exp.body != null)
194: exp.body = (Expression) exp.body.walk(this );
195: } finally {
196: inTailContext = save;
197: currentLambda = parent;
198: }
199:
200: walkDecls(exp);
201:
202: for (LambdaExp child = exp.firstChild; child != null; child = child.nextSibling) {
203: if (child.getCanRead() || child.isClassMethod()
204: || child.min_args != child.max_args)
205: child.flags |= LambdaExp.CANNOT_INLINE;
206: else {
207: ApplyExp caller = child.returnContinuation;
208: if (caller != LambdaExp.unknownContinuation
209: && !comp.usingCPStyle()) {
210: child.setInlineOnly(true);
211: }
212: }
213: }
214:
215: for (LambdaExp child = exp.firstChild; child != null; child = child.nextSibling) {
216: if ((child.flags & (LambdaExp.CANNOT_INLINE | LambdaExp.INLINE_ONLY)) != 0)
217: continue;
218: // We can inline child if it is a member of a set of functions
219: // which can all be inlined in the same method, and for which
220: // all callers are known and members of the same set,
221: // and each function has at most one caller that is not a tail-call.
222: // FIXME Basic algorithm:
223: /*
224: Vector inlineSet = new Vector(); // empty
225: ApplyExp[] apl = (ApplyExp[]) applications.get(child);
226: Stack queue = new Stack();
227: copy elements of apl to queue;
228: while (!queue.empty())
229: {
230: LambdaExp caller = (LambdaExp) queue.pop();
231: if ((caller.flags & LambdaExp.CANNOT_INLINE) != 0)
232: {
233: child.flags |= LambdaExp.CANNOT_INLINE;
234: break;
235: }
236: if (caller in inlineSet)
237: continue;
238: apl = (ApplyExp[]) applications.get(child);
239: add elements of apl to queue;
240: add caller to inlineSet;
241: add caller.returnContinuation.context to inlineSet;
242: }
243: */
244: }
245: }
246:
247: // Map LambdaExp to ApplyExp[], which is the set of non-self tails
248: // calls that call the key.
249: // Hashtable applications = new Hashtable();
250:
251: protected Expression walkClassExp(ClassExp exp) {
252: boolean save = inTailContext;
253: LambdaExp parent = currentLambda;
254: currentLambda = exp;
255: exp.setCanRead(true);
256: try {
257: inTailContext = false;
258: for (LambdaExp child = exp.firstChild; child != null
259: && exitValue == null; child = child.nextSibling)
260: walkLambdaExp(child, false);
261: } finally {
262: inTailContext = save;
263: currentLambda = parent;
264: }
265:
266: return exp;
267: }
268:
269: protected Expression walkReferenceExp(ReferenceExp exp) {
270: Declaration decl = Declaration.followAliases(exp.binding);
271: if (decl != null) {
272: // Replace references to a void variable (including one whose value
273: // is the empty sequence in XQuery) by an empty constant. This is
274: // not so much an optimization as avoiding the complications and
275: // paradoxes of variables and expression that are void.
276: if (decl.type == Type.void_type)
277: return QuoteExp.voidExp;
278: decl.setCanRead(true);
279: }
280: Declaration ctx = exp.contextDecl();
281: if (ctx != null)
282: ctx.setCanRead(true);
283: return exp;
284: }
285:
286: final Expression walkSetExp(Declaration decl, Expression value) {
287: if (decl != null && decl.getValue() == value
288: && value instanceof LambdaExp
289: && !(value instanceof ClassExp) && !decl.isPublic()) {
290: LambdaExp lexp = (LambdaExp) value;
291: walkLambdaExp(lexp, false);
292: return lexp;
293: } else
294: return (Expression) value.walk(this );
295: }
296:
297: protected Expression walkSetExp(SetExp exp) {
298: boolean save = inTailContext;
299: try {
300: inTailContext = false;
301: Declaration decl = exp.binding;
302: if (decl != null && decl.isAlias()) {
303: if (exp.isDefining()) {
304: exp.new_value = (Expression) exp.new_value
305: .walk(this );
306: return exp;
307: }
308: decl = Declaration.followAliases(decl);
309: }
310: if (decl != null)
311: decl.setCanWrite();
312: Declaration ctx = exp.contextDecl();
313: if (ctx != null)
314: ctx.setCanRead(true);
315: Expression value = walkSetExp(decl, exp.new_value);
316: if (decl != null
317: && decl.context instanceof LetExp
318: && value == decl.getValue()
319: && (value instanceof LambdaExp || value instanceof QuoteExp)) {
320: // The assignment is redundant, as it has been moved to the
321: // initialization of the LetExp.
322: return QuoteExp.voidExp;
323: }
324: exp.new_value = value;
325: return exp;
326: } finally {
327: inTailContext = save;
328: }
329: }
330:
331: protected Expression walkTryExp(TryExp exp) {
332: boolean save = inTailContext;
333: try {
334: inTailContext = false;
335: return super .walkTryExp(exp);
336: } finally {
337: inTailContext = save;
338: }
339: }
340:
341: protected Expression walkSynchronizedExp(SynchronizedExp exp) {
342: boolean save = inTailContext;
343: try {
344: inTailContext = false;
345: return super.walkSynchronizedExp(exp);
346: } finally {
347: inTailContext = save;
348: }
349: }
350: }
|