001: package gnu.expr;
002:
003: /** Does setTailCall on ApplyExp's that are tail-calls.
004: Also setCanRead, setCanCall, setCanWrite on Declarations
005: and setCanRead, setCanCall on LambdaExp when appropriate. */
006:
007: public class FindTailCalls extends ExpWalker {
008: public static void findTailCalls(Expression exp) {
009: FindTailCalls walker = new FindTailCalls();
010: exp.walk(walker);
011: //or: walter.walkExpression(exp);
012: }
013:
014: boolean inTailContext = true;
015:
016: protected Expression walkApplyExp(ApplyExp exp) {
017: if (inTailContext)
018: exp.setTailCall(true);
019: exp.context = currentLambda;
020: boolean save = inTailContext;
021: LambdaExp lexp = null;
022: try {
023: inTailContext = false;
024: if (exp.func instanceof ReferenceExp) {
025: ReferenceExp func = (ReferenceExp) exp.func;
026: Declaration binding = Declaration
027: .followAliases(func.binding);
028: if (binding != null) {
029: exp.nextCall = binding.firstCall;
030: binding.firstCall = exp;
031: binding.setCanCall();
032: Expression value = binding.getValue();
033: if (value instanceof LambdaExp)
034: lexp = (LambdaExp) value;
035: }
036: } else if (exp.func instanceof LambdaExp) {
037: lexp = (LambdaExp) exp.func;
038: walkLambdaExp(lexp, false);
039: lexp.setCanCall(true);
040: } else
041: exp.func = (Expression) exp.func.walk(this );
042: if (lexp != null) {
043: if (lexp.returnContinuation == exp)
044: ; // OK
045: else if (lexp == currentLambda && save)
046: ; // (Self-)tail-recursion is OK.
047: else if (lexp.returnContinuation == null)
048: lexp.returnContinuation = exp;
049: else
050: lexp.returnContinuation = LambdaExp.unknownContinuation;
051: }
052: exp.args = walkExps(exp.args);
053: return exp;
054: } finally {
055: inTailContext = save;
056: }
057: }
058:
059: protected Expression walkBeginExp(BeginExp exp) {
060: boolean save = inTailContext;
061: try {
062: int n = exp.length - 1;
063: for (int i = 0; i <= n; i++) {
064: inTailContext = (i == n) && save;
065: exp.exps[i] = (Expression) exp.exps[i].walk(this );
066: }
067: return exp;
068: } finally {
069: inTailContext = save;
070: }
071: }
072:
073: protected Expression walkFluidLetExp(FluidLetExp exp) {
074: for (Declaration decl = exp.firstDecl(); decl != null; decl = decl
075: .nextDecl()) {
076: decl.setCanRead(true);
077: decl.setCanWrite(true);
078: }
079: return super .walkFluidLetExp(exp);
080: }
081:
082: protected Expression walkLetExp(LetExp exp) {
083: int n = exp.inits.length;
084: boolean save = inTailContext;
085: Declaration decl;
086: try {
087: inTailContext = false;
088:
089: decl = exp.firstDecl();
090: for (int i = 0; i < n; i++, decl = decl.nextDecl())
091: exp.inits[i] = walkSetExp(decl, exp.inits[i]);
092: } finally {
093: inTailContext = save;
094: }
095: exp.body = (Expression) exp.body.walk(this );
096: walkDecls(exp);
097: return exp;
098: }
099:
100: public void walkDecls(ScopeExp exp) {
101: Declaration decl = exp.firstDecl();
102: for (; decl != null; decl = decl.nextDecl()) {
103: Expression value = decl.getValue();
104: if (value != null && value instanceof LambdaExp) {
105: LambdaExp lexp = (LambdaExp) value;
106: if (decl.getCanRead())
107: lexp.setCanRead(true);
108: if (decl.getCanCall())
109: lexp.setCanCall(true);
110: }
111: }
112: }
113:
114: protected Expression walkIfExp(IfExp exp) {
115: boolean save = inTailContext;
116: try {
117: inTailContext = false;
118: exp.test = (Expression) exp.test.walk(this );
119: } finally {
120: inTailContext = save;
121: }
122: exp.then_clause = (Expression) exp.then_clause.walk(this );
123: Expression else_clause = exp.else_clause;
124: if (else_clause != null)
125: exp.else_clause = (Expression) else_clause.walk(this );
126: return exp;
127: }
128:
129: protected Expression walkLambdaExp(LambdaExp exp) {
130: walkLambdaExp(exp, true);
131: return exp;
132: }
133:
134: final void walkLambdaExp(LambdaExp exp, boolean canRead) {
135: boolean save = inTailContext;
136: LambdaExp parent = currentLambda;
137: currentLambda = exp;
138: if (canRead)
139: exp.setCanRead(true);
140: try {
141: inTailContext = false;
142: if (exp.defaultArgs != null)
143: exp.defaultArgs = walkExps(exp.defaultArgs);
144: inTailContext = exp.getInlineOnly() ? save : true;
145: if (exitValue == null && exp.body != null)
146: exp.body = (Expression) exp.body.walk(this );
147: } finally {
148: inTailContext = save;
149: currentLambda = parent;
150: }
151:
152: walkDecls(exp);
153:
154: for (LambdaExp child = exp.firstChild; child != null; child = child.nextSibling) {
155: if (child.getCanRead() || child.min_args != child.max_args)
156: child.flags |= LambdaExp.CANNOT_INLINE;
157: else {
158: ApplyExp caller = child.returnContinuation;
159: if (caller != LambdaExp.unknownContinuation
160: && !Compilation.usingCPStyle()) {
161: child.setInlineOnly(true);
162: }
163: }
164: }
165:
166: for (LambdaExp child = exp.firstChild; child != null; child = child.nextSibling) {
167: if ((child.flags & (LambdaExp.CANNOT_INLINE | LambdaExp.INLINE_ONLY)) != 0)
168: continue;
169: // We can inline child if it is a member of a set of functions
170: // which can all be inlined in the same method, and for which
171: // all callers are known and members of the same,
172: // and each function has at most one caller that is not a tail-call.
173: // FIXME Basic algorithm:
174: /*
175: Vector inlineSet = new Vector(); // empty
176: ApplyExp[] apl = (ApplyExp[]) applications.get(child);
177: Stack queue = new Stack();
178: copy elements of apl to queue;
179: while (!queue.empty())
180: {
181: LambdaExp caller = (LambdaExp) queue.pop();
182: if ((caller.flags & LambdaExp.CANNOT_INLINE) != 0)
183: {
184: child.flags |= LambdaExp.CANNOT_INLINE;
185: break;
186: }
187: if (caller in inlineSet)
188: continue;
189: apl = (ApplyExp[]) applications.get(child);
190: add elements of apl to queue;
191: add caller to inlineSet;
192: add caller.returnContinuation.context to inlineSet;
193: }
194: */
195: }
196: }
197:
198: // Map LambdaExp to ApplyExp[], which is the set of non-self tails
199: // calls that call the key.
200: // Hashtable applications = new Hashtable();
201:
202: protected Expression walkClassExp(ClassExp exp) {
203: boolean save = inTailContext;
204: LambdaExp parent = currentLambda;
205: currentLambda = exp;
206: exp.setCanRead(true);
207: try {
208: inTailContext = false;
209: for (LambdaExp child = exp.firstChild; child != null
210: && exitValue == null; child = child.nextSibling)
211: walkLambdaExp(child, false);
212: } finally {
213: inTailContext = save;
214: currentLambda = parent;
215: }
216:
217: return exp;
218: }
219:
220: protected Expression walkReferenceExp(ReferenceExp exp) {
221: Declaration decl = Declaration.followAliases(exp.binding);
222: if (decl != null)
223: decl.setCanRead(true);
224: return exp;
225: }
226:
227: final Expression walkSetExp(Declaration decl, Expression value) {
228: if (decl != null)
229: decl.setCanWrite();
230: if (decl != null && decl.getValue() == value
231: && value instanceof LambdaExp
232: && !(value instanceof ObjectExp) && !decl.isPublic()) {
233: LambdaExp lexp = (LambdaExp) value;
234: walkLambdaExp(lexp, false);
235: return lexp;
236: } else
237: return (Expression) value.walk(this );
238: }
239:
240: protected Expression walkSetExp(SetExp exp) {
241: boolean save = inTailContext;
242: try {
243: inTailContext = false;
244: Expression declValue;
245: Declaration decl = exp.binding;
246: if (decl != null && decl.isAlias()) {
247: if (exp.isDefining())
248: return exp;
249: decl = Declaration.followAliases(decl);
250:
251: }
252: exp.new_value = walkSetExp(decl, exp.new_value);
253: return exp;
254: } finally {
255: inTailContext = save;
256: }
257: }
258:
259: protected Expression walkTryExp(TryExp exp) {
260: boolean save = inTailContext;
261: try {
262: inTailContext = false;
263: return super .walkTryExp(exp);
264: } finally {
265: inTailContext = save;
266: }
267: }
268:
269: protected Expression walkSynchronizedExp(SynchronizedExp exp) {
270: boolean save = inTailContext;
271: try {
272: inTailContext = false;
273: return super.walkSynchronizedExp(exp);
274: } finally {
275: inTailContext = save;
276: }
277: }
278: }
|