001: package gnu.expr;
002:
003: import java.util.Hashtable;
004:
005: public class FindCapturedVars extends ExpWalker {
006: public static void findCapturedVars(Expression exp) {
007: exp.walk(new FindCapturedVars());
008: }
009:
010: protected Expression walkApplyExp(ApplyExp exp) {
011: boolean skipFunc = false;
012: // If the func is bound to a module-level known function, and it
013: // doesn't need a closure yet (i.e. could be compiled to a static
014: // method), don't walk the function, since that might force it to
015: // unnecessarily get "captured" which might force the current
016: // function to require a closure. That would be wasteful if the
017: // alternative is to just call func using invokestatic. (It is
018: // possible that we later find out that func needs a static link,
019: // in which case the current function does as well; this is taken
020: // care of by calling setCallersNeedStaticLink in LambdaExp.)
021: if (exp.func instanceof ReferenceExp
022: && !Compilation.usingTailCalls) {
023: Declaration decl = Declaration
024: .followAliases(((ReferenceExp) exp.func).binding);
025: if (decl != null && decl.context instanceof ModuleExp) {
026: Expression value = decl.getValue();
027: if (value instanceof LambdaExp) {
028: LambdaExp lexp = (LambdaExp) value;
029: LambdaExp cur = getCurrentLambda();
030: if (!lexp.getNeedsClosureEnv())
031: skipFunc = true;
032: }
033: }
034: }
035: if (!skipFunc)
036: exp.func = (Expression) exp.func.walk(this );
037: if (exitValue == null)
038: exp.args = walkExps(exp.args);
039: return exp;
040: }
041:
042: public void walkDefaultArgs(LambdaExp exp) {
043: if (exp.defaultArgs == null)
044: return;
045:
046: super .walkDefaultArgs(exp);
047:
048: // Check if any default expression "captured" a parameters.
049: // If so, evaluating a default expression cannot be done until the
050: // heapFrame is allocated in the main-method. But in most cases, a
051: // default expression will not contain a nested scope, hence no
052: // capture, hence we can generate efficient code to handle optional
053: // arguments.
054: for (Declaration param = exp.firstDecl(); param != null; param = param
055: .nextDecl()) {
056: if (!param.isSimple()) {
057: exp.setFlag(true, LambdaExp.DEFAULT_CAPTURES_ARG);
058: break;
059: }
060: }
061: }
062:
063: protected Expression walkModuleExp(ModuleExp exp) {
064: ModuleExp saveModule = currentModule;
065: Hashtable saveDecls = unknownDecls;
066: currentModule = exp;
067: unknownDecls = null;
068: try {
069: return walkLambdaExp(exp);
070: } finally {
071: if (unknownDecls != null) {
072: int count = unknownDecls.size();
073: java.util.Enumeration e = unknownDecls.keys();
074: int i = 0;
075: Expression[] init = new Expression[1];
076: LetExp let = new LetExp(init);
077: Declaration env = let.addDeclaration("env$",
078: Compilation.typeEnvironment);
079: init[0] = new ApplyExp(
080: Compilation.getCurrentEnvironmentMethod,
081: Expression.noExpressions);
082: env.setCanRead(true);
083: env.noteValue(init[0]);
084: Expression[] exps = new Expression[count + 1];
085: for (; e.hasMoreElements(); i++) {
086: String id = (String) e.nextElement();
087: Declaration decl = (Declaration) unknownDecls
088: .get(id);
089: Expression[] args = new Expression[2];
090: args[0] = new ReferenceExp(env);
091: args[1] = new QuoteExp(id);
092: SetExp set = new SetExp(decl, new ApplyExp(
093: Compilation.getBindingEnvironmentMethod,
094: args));
095: set.setDefining(true);
096: exps[i] = set;
097: }
098: exps[i] = currentModule.body;
099: let.setBody(new BeginExp(exps));
100: currentModule.body = let;
101: }
102: currentModule = saveModule;
103: unknownDecls = saveDecls;
104: }
105: }
106:
107: protected Expression walkFluidLetExp(FluidLetExp exp) {
108: for (Declaration decl = exp.firstDecl(); decl != null; decl = decl
109: .nextDecl()) {
110: Declaration bind = allocUnboundDecl(decl.getName());
111: capture(bind);
112: decl.base = bind;
113: }
114: return super .walkLetExp(exp);
115: }
116:
117: protected Expression walkLetExp(LetExp exp) {
118: if (exp.body instanceof BeginExp) {
119: // Optimize "letrec"-like forms.
120: // If init[i] is the magic QuoteExp.nullExp, and the real value
121: // is a LambdaExp or a QuoteExp, we're not going to get weird
122: // order-dependencies, and it is safe to transform it to a regular let.
123: Expression[] inits = exp.inits;
124: int len = inits.length;
125: BeginExp bexp = (BeginExp) exp.body;
126: Expression[] exps = bexp.exps;
127: if (bexp.length > len) {
128: int i = 0;
129: Declaration decl = exp.firstDecl();
130: for (; i < len; decl = decl.nextDecl(), i++) {
131: if (inits[i] == QuoteExp.nullExp
132: && exps[i] instanceof SetExp) {
133: SetExp set = (SetExp) exps[i];
134: if ((set.new_value instanceof LambdaExp || set.new_value instanceof QuoteExp)
135: && set.binding == decl) {
136: inits[i] = set.new_value;
137: exps[i] = QuoteExp.voidExp;
138: }
139: }
140: }
141: }
142: }
143: return super .walkLetExp(exp);
144: }
145:
146: public void capture(Declaration decl) {
147: if (!(decl.getCanRead() || decl.getCanCall()))
148: return;
149:
150: if (decl.getFlag(Declaration.IS_UNKNOWN))
151: return; // FIXME - for now, as long as unknows are static
152: if (decl.field != null && decl.field.getStaticFlag())
153: return;
154: if (decl.getFlag(Declaration.IS_CONSTANT)
155: && decl.getValue() instanceof QuoteExp)
156: return;
157:
158: LambdaExp curLambda = getCurrentLambda();
159: LambdaExp declLambda = decl.getContext().currentLambda();
160:
161: // If curLambda is inlined, the function that actually needs a closure
162: // is its caller. We get its caller using returnContinuation.context.
163: // A complication is that we can have a chain of functions that
164: // recursively call each other, and are hence inlined in each other.
165: // Since a function is only inlined if it has a single call site,
166: // that means there is actually no way to actually enter the chain;
167: // i.e. none of the inlined functions can actually get called.
168: // However, we have to watch out for this possibility, or the loop
169: // here will run forever. For us to have a cycle, all of the functions
170: // must have the same parent. If the loop is executed more times
171: // than the number of child functions of the parent, then we know we
172: // have a cycle.
173: // The `chain' variable is used to catch infinite inline loops by
174: // iterating through the parents children.
175: LambdaExp oldParent = null;
176: LambdaExp chain = null;
177: while (curLambda != declLambda && curLambda.getInlineOnly()) {
178: LambdaExp curParent = curLambda.outerLambda();
179: if (curParent != oldParent) {
180: // Reset the chain.
181: chain = curParent.firstChild;
182: oldParent = curParent;
183: }
184: ApplyExp curReturn = curLambda.returnContinuation;
185: if (chain == null || curReturn == null) {
186: // Infinite loop of functions that are inlined in each other.
187: curLambda.setCanCall(false);
188: return;
189: }
190: curLambda = curReturn.context;
191: chain = chain.nextSibling;
192: }
193: if (Compilation.usingCPStyle()) {
194: if (curLambda instanceof ModuleExp)
195: return;
196: } else if (curLambda == declLambda)
197: return;
198:
199: // The logic here is similar to that of decl.ignorable():
200: Expression value = decl.getValue();
201: LambdaExp declValue;
202: if (value == null || !(value instanceof LambdaExp))
203: declValue = null;
204: else {
205: declValue = (LambdaExp) value;
206: if (declValue.getInlineOnly())
207: return;
208: if (declValue.isHandlingTailCalls())
209: declValue = null;
210: else if (declValue == curLambda && !decl.getCanRead())
211: return;
212: }
213: if (decl.getFlag(Declaration.STATIC_SPECIFIED))
214: decl.setSimple(false);
215: else if (decl.getCanRead() || declValue == null) {
216: LambdaExp heapLambda = curLambda;
217: heapLambda.setImportsLexVars();
218: LambdaExp parent = heapLambda.outerLambda();
219: for (LambdaExp outer = parent; outer != declLambda
220: && outer != null;) {
221: heapLambda = outer;
222: if (!decl.getCanRead() && declValue == outer)
223: break;
224: heapLambda.setNeedsStaticLink();
225: outer = heapLambda.outerLambda();
226: }
227: if (decl.base != null) {
228: decl.base.setCanRead(true);
229: capture(decl.base);
230: }
231: if (decl.isSimple()) {
232: if (declLambda.capturedVars == null
233: && !(declLambda instanceof ModuleExp || declLambda instanceof ClassExp)) {
234: declLambda.heapFrame = new gnu.bytecode.Variable(
235: "heapFrame");
236: declLambda.heapFrame.setArtificial(true);
237: }
238: decl.setSimple(false);
239: if (!decl.isPublic()) {
240: decl.nextCapturedVar = declLambda.capturedVars;
241: declLambda.capturedVars = decl;
242: }
243: }
244: }
245: }
246:
247: Hashtable unknownDecls = null;
248: ModuleExp currentModule = null;
249:
250: Declaration allocUnboundDecl(String name) {
251: Declaration decl;
252: if (unknownDecls == null) {
253: unknownDecls = new Hashtable(100);
254: decl = null;
255: } else
256: decl = (Declaration) unknownDecls.get(name);
257: if (decl == null) {
258: decl = currentModule.addDeclaration(name);
259: decl.setSimple(false);
260: decl.setPrivate(true);
261: if (currentModule.isStatic())
262: decl.setFlag(Declaration.STATIC_SPECIFIED);
263: decl.setCanRead(true);
264: decl.setFlag(Declaration.IS_UNKNOWN);
265: decl.setIndirectBinding(true);
266: unknownDecls.put(name, decl);
267: }
268: return decl;
269: }
270:
271: protected Expression walkReferenceExp(ReferenceExp exp) {
272: Declaration decl = exp.getBinding();
273: if (decl == null) {
274: decl = allocUnboundDecl(exp.getName());
275: exp.setBinding(decl);
276: } else
277: // FIXME remove else when IS_UNKNOWN decls are non-static
278: capture(Declaration.followAliases(decl));
279: return exp;
280: }
281:
282: protected Expression walkThisExp(ThisExp exp) {
283: // This can be captured like any other variable.
284: if (exp.getBinding() != null)
285: capture(exp.getBinding());
286: return exp;
287: }
288:
289: protected Expression walkSetExp(SetExp exp) {
290: Declaration decl = exp.binding;
291: if (decl == null) {
292: decl = allocUnboundDecl(exp.getName());
293: exp.binding = decl;
294: } else
295: // FIXME remove else when IS_UNKNOWN decls are non-static
296: capture(Declaration.followAliases(decl));
297: return super .walkSetExp(exp);
298: }
299:
300: public Expression walkIncrementExp(IncrementExp exp) {
301: Declaration decl = Declaration.followAliases(exp.decl);
302: if (decl != null)
303: capture(decl);
304: return super.walkIncrementExp(exp);
305: }
306: }
|