]> gerrit.simantics Code Review - simantics/platform.git/blob
68dd82f15f4bb1c76d5b68c07f58cfc501e3f66c
[simantics/platform.git] /
1 package org.simantics.scl.compiler.internal.codegen.ssa;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5
6 import org.cojen.classfile.TypeDesc;
7 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
8 import org.simantics.scl.compiler.internal.codegen.continuations.Cont;
9 import org.simantics.scl.compiler.internal.codegen.continuations.ContRef;
10 import org.simantics.scl.compiler.internal.codegen.continuations.ReturnCont;
11 import org.simantics.scl.compiler.internal.codegen.references.BoundVar;
12 import org.simantics.scl.compiler.internal.codegen.references.Val;
13 import org.simantics.scl.compiler.internal.codegen.references.ValRef;
14 import org.simantics.scl.compiler.internal.codegen.ssa.exits.Jump;
15 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;
16 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetFunctions;
17 import org.simantics.scl.compiler.internal.codegen.types.JavaTypeTranslator;
18 import org.simantics.scl.compiler.internal.codegen.utils.CopyContext;
19 import org.simantics.scl.compiler.internal.codegen.utils.MethodBuilder;
20 import org.simantics.scl.compiler.internal.codegen.utils.PrintingContext;
21 import org.simantics.scl.compiler.internal.codegen.utils.SSALambdaLiftingContext;
22 import org.simantics.scl.compiler.internal.codegen.utils.SSASimplificationContext;
23 import org.simantics.scl.compiler.internal.codegen.utils.SSAValidationContext;
24 import org.simantics.scl.compiler.internal.codegen.utils.ValRefVisitor;
25 import org.simantics.scl.compiler.types.TVar;
26 import org.simantics.scl.compiler.types.Type;
27 import org.simantics.scl.compiler.types.Types;
28
29 public final class SSAFunction extends SSAClosure {
30     TVar[] typeParameters;
31     Type effect;
32     SSABlock firstBlock;
33     SSABlock lastBlock;
34     ReturnCont returnCont;
35     
36     public SSAFunction(TVar[] typeParameters, Type effect, Type returnType) {
37         this(typeParameters, effect, new ReturnCont(returnType));
38     }
39         
40     public SSAFunction(TVar[] typeParameters, Type effect, ReturnCont returnCont) {
41         this.typeParameters = typeParameters;
42         this.returnCont = returnCont;
43         this.effect = Types.canonical(effect);
44         returnCont.setParent(this);
45     }
46     
47     public boolean hasEffect() {
48         return effect != Types.NO_EFFECTS;
49     }
50     
51     public void addBlock(SSABlock block) {
52         block.parent = this;
53         if(lastBlock == null) {
54             firstBlock = lastBlock = block;
55             block.next = block.prev = null;            
56         }
57         else {
58             lastBlock.next = block;
59             block.prev = lastBlock;
60             block.next = null;
61             lastBlock = block;
62         }
63     }
64     
65     public void addBlockInFront(SSABlock block) {
66         block.parent = this;
67         if(firstBlock == null) {
68             firstBlock = lastBlock = block;
69             block.next = block.prev = null;            
70         }
71         else {
72             firstBlock.prev = block;
73             block.next = firstBlock;
74             block.prev = null;
75             firstBlock = block;
76         }
77     }
78
79     public ReturnCont getReturnCont() {
80         return returnCont;
81     }
82     
83     public TVar[] getTypeParameters() {
84         return typeParameters;
85     }
86     
87     public SSABlock getFirstBlock() {
88         return firstBlock;
89     }
90     
91     public void generateCode(MethodBuilder mb) {
92         JavaTypeTranslator tt = mb.getJavaTypeTranslator();
93         for(int i=0,j=0;i<firstBlock.parameters.length;++i)
94             if(!tt.toTypeDesc(firstBlock.parameters[i].getType()).equals(TypeDesc.VOID))
95                 mb.setLocalVariable(firstBlock.parameters[i], mb.getParameter(j++));
96         generateCodeWithAlreadyPreparedParameters(mb);
97     }
98     
99     public void generateCodeWithAlreadyPreparedParameters(MethodBuilder mb) {
100         for(SSABlock block = firstBlock; block != null; block = block.next)
101             block.prepare(mb);
102         firstBlock.generateCode(mb);
103     }
104
105     public void toString(PrintingContext context) {
106         context.indentation();
107         if(typeParameters.length > 0) {            
108             context.append('<');
109             boolean first = true;
110             for(TVar var : typeParameters) {
111                 if(first)
112                     first = false;
113                 else
114                     context.append(',');
115                 context.append(var);
116             }
117             context.append("> ");
118         }
119         if(hasEffect()) {
120             context.append(effect);
121             context.append(" ");
122         }
123         context.append("RETURNS ");
124         context.append(returnCont.getType());
125         context.append('\n');
126         
127         // Print blocks
128         context.pushBlockQueue();
129         context.addBlock(getFirstBlock());
130         while(true) {
131             SSABlock block = context.pollBlock();
132             if(block == null)
133                 break;
134             block.toString(context);
135         }
136         context.popBlockQueue();
137     }
138     
139     @Override
140     public String toString() {
141         PrintingContext context = new PrintingContext();
142         toString(context);
143         return context.toString();
144     }
145     
146     public void validate(SSAValidationContext context) {
147         if(target instanceof BoundVar && ((BoundVar)target).parent != this)
148             throw new InternalCompilerError();
149         
150         // Add valid type variables
151         for(TVar var : typeParameters)
152             context.validTypeVariables.add(var);
153         
154         // Add valid variables and continuations
155         context.validContinuations.add(returnCont);        
156         for(SSABlock block = firstBlock; block != null; block = block.next) {            
157             context.validContinuations.add(block);  
158             for(BoundVar parameter : block.parameters)
159                 context.validBoundVariables.add(parameter);
160             for(SSAStatement stat = block.firstStatement; stat != null; stat = stat.next)
161                 stat.addBoundVariablesTo(context);
162         }
163
164         // Validate blocks
165         for(SSABlock block = firstBlock; block != null; block = block.next)
166             block.validate(context);
167         context.validate(returnCont);
168         
169         //context.reset(); // FIXME not good when there are nested functions
170     }
171     
172     @Override
173     public void simplify(SSASimplificationContext context) {
174         for(SSABlock block = firstBlock; block != null; block = block.next)
175             block.simplify(context);
176         if(firstBlock == lastBlock && firstBlock.firstStatement == firstBlock.lastStatement &&
177                 firstBlock.firstStatement instanceof LetFunctions) {
178             simplifySingleLambda(context);            
179         }
180     }
181     
182     private void simplifySingleLambda(SSASimplificationContext context) {
183         LetFunctions letF = (LetFunctions)firstBlock.firstStatement;
184         if(!(letF.getFirstClosure() instanceof SSAFunction))
185             return;
186         SSAFunction f = (SSAFunction)letF.getFirstClosure();
187         if(f.getNext() != null)
188             return;
189         Val fVal = f.getTarget();
190         if(!firstBlock.exit.isJump(getReturnCont(), fVal))
191             return;
192         if(fVal.hasMoreThanOneOccurences())
193             return; // Possible if function is recursive and refers to itself
194         if(hasEffect())
195             return; // Not probably possible (?)
196                 
197         // Transform
198         for(SSABlock block = f.firstBlock; block != null; block = block.next)
199             block.parent = this;
200         lastBlock.next = f.firstBlock;
201         f.firstBlock.prev = lastBlock;        
202         lastBlock = f.lastBlock;
203         
204         firstBlock.firstStatement = firstBlock.lastStatement = null;
205         setReturnCont(f.getReturnCont());        
206         effect = f.effect;
207         BoundVar[] newParameters = BoundVar.copy(f.firstBlock.parameters);
208         firstBlock.setParameters(BoundVar.concat(getParameters(), newParameters));
209         firstBlock.setExit(new Jump(f.firstBlock.createOccurrence(), ValRef.createOccurrences(newParameters)));
210         context.markModified("SSAFunction.simplify-simple-lambda");
211     }
212
213     public void setReturnCont(ReturnCont returnCont) {
214         this.returnCont = returnCont;
215         returnCont.setParent(this);
216     }
217
218     public ValRef isEqualToConstant() {
219         if(firstBlock.parameters.length > 0)
220             return null;
221         if(firstBlock != lastBlock)
222             return null;
223         if(firstBlock.firstStatement != null)
224             return null;
225         if(!(firstBlock.exit instanceof Jump))
226             return null;
227         Jump exit = (Jump)firstBlock.exit;
228         if(exit.getTarget().getBinding() != returnCont)
229             return null;
230         return exit.getParameters()[0];
231     }    
232
233     public BoundVar[] getParameters() {
234         return firstBlock.parameters;                
235     }
236     
237     public Type[] getParameterTypes() {
238         return Types.getTypes(firstBlock.parameters);                
239     }
240
241     public int getArity() {
242         return firstBlock.parameters.length;
243     }
244
245     @Override
246     public void markGenerateOnFly() {
247         for(SSABlock block = firstBlock; block != null; block = block.next)
248             block.markGenerateOnFly();
249     }
250
251     @Override
252     public SSAClosure copy(CopyContext context) {
253         TVar[] newTypeParameters = context.copyParameters(typeParameters);
254         SSAFunction newFunction = new SSAFunction(newTypeParameters, effect, context.copy(returnCont));
255         for(SSABlock block = firstBlock;
256                 block != null; block = block.next)
257             newFunction.addBlock(context.copy(block));
258         return newFunction;
259     }
260     
261     @Override
262     public void replace(TVar[] vars, Type[] replacements) {
263         returnCont.replace(vars, replacements);
264         for(SSABlock block = firstBlock;
265                 block != null; block = block.next)
266             block.replace(vars, replacements);
267     }
268
269     public void setTypeParameters(TVar[] typeParameters) {
270         this.typeParameters = typeParameters;
271     }
272
273     @Override
274     public Type getType() {
275         Type type = returnCont.getType();
276         type = Types.functionE(
277                 Types.getTypes(firstBlock.parameters),
278                 effect,
279                 type);
280         type = Types.forAll(typeParameters, type);
281         return type;
282     }
283
284     public void mergeBlocks(SSAFunction function) {
285         SSABlock block = function.firstBlock;
286         while(block != null) {
287             SSABlock next = block.next;
288             addBlock(block);
289             block = next;
290         }
291     }
292
293     public Type getReturnType() {
294         return returnCont.getType();
295     }
296
297     @Override
298     public void destroy() {
299         for(SSABlock block = firstBlock;
300                 block != null; block = block.next)
301             block.destroy();
302     }
303     
304     @Override    
305     public void collectFreeVariables(ArrayList<ValRef> vars) {
306         for(SSABlock block = firstBlock;
307                 block != null; block = block.next)
308             block.collectFreeVariables(this, vars);
309     }
310     
311     @Override    
312     public void lambdaLift(SSALambdaLiftingContext context) {
313         for(SSABlock block = firstBlock;
314                 block != null; block = block.next)
315             block.lambdaLift(context);
316     }
317
318     @Override
319     public void parametrize(BoundVar[] parameters) {
320         Cont proxy = null;
321         for(ContRef ref = firstBlock.getOccurrence(); ref != null; ref = ref.getNext())
322             proxy = ref.addParametersInFront(parameters, firstBlock.parameters, proxy);
323         
324         firstBlock.parameters = BoundVar.concat(parameters, firstBlock.parameters);
325         for(BoundVar parameter : parameters)
326             parameter.parent = firstBlock;
327     }
328     
329     public void apply(ValRef[] parameters) {
330         if(parameters.length == 0)
331             return;
332         if(firstBlock.hasNoOccurences()) {
333             BoundVar[] vars = firstBlock.getParameters();
334             for(int i=0;i<parameters.length;++i)
335                 vars[i].replaceBy(parameters[i]);
336             firstBlock.setParameters(Arrays.copyOfRange(vars, parameters.length, vars.length));
337         }
338         else {
339             BoundVar[] newVars = new BoundVar[getArity()-parameters.length];
340             SSABlock block = new SSABlock(newVars);
341             block.setExit(new Jump(firstBlock.createOccurrence(), 
342                     ValRef.concat(ValRef.copy(parameters), ValRef.createOccurrences(newVars))));
343             addBlockInFront(block);
344         }
345     }
346
347     public void applyTypes(Type[] types) {
348         if(types.length == 0)
349             return;
350         if(types.length == typeParameters.length) {
351             replace(typeParameters, types);
352             typeParameters = TVar.EMPTY_ARRAY;
353         }
354         else {
355             replace(Arrays.copyOf(typeParameters, types.length), types);
356             typeParameters = 
357                     Arrays.copyOfRange(typeParameters, 
358                             types.length, typeParameters.length);
359         }            
360     }
361     
362     public boolean isSimpleEnoughForInline() {
363         return firstBlock == lastBlock && 
364                 (firstBlock.firstStatement == null || 
365                 (firstBlock.firstStatement == firstBlock.lastStatement
366                 && firstBlock.firstStatement instanceof LetApply));
367     }
368
369     public Type getEffect() {
370         return effect;
371     }
372
373     @Override
374     public boolean isValue() {
375         return getArity() == 0;
376     }
377
378     @Override
379     public void forValRefs(ValRefVisitor visitor) {
380         for(SSABlock block = firstBlock;
381                 block != null; block = block.next)
382             block.forValRefs(visitor);
383     }
384
385 }