]> gerrit.simantics Code Review - simantics/platform.git/blob
c812db7c4476a3b8078847ad045d359cf618afc3
[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.binders.BoundVarBinder;
15 import org.simantics.scl.compiler.internal.codegen.ssa.binders.FunctionBinder;
16 import org.simantics.scl.compiler.internal.codegen.ssa.exits.Jump;
17 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;
18 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetFunctions;
19 import org.simantics.scl.compiler.internal.codegen.types.JavaTypeTranslator;
20 import org.simantics.scl.compiler.internal.codegen.utils.CopyContext;
21 import org.simantics.scl.compiler.internal.codegen.utils.MethodBuilder;
22 import org.simantics.scl.compiler.internal.codegen.utils.Printable;
23 import org.simantics.scl.compiler.internal.codegen.utils.PrintingContext;
24 import org.simantics.scl.compiler.internal.codegen.utils.SSALambdaLiftingContext;
25 import org.simantics.scl.compiler.internal.codegen.utils.SSASimplificationContext;
26 import org.simantics.scl.compiler.internal.codegen.utils.SSAValidationContext;
27 import org.simantics.scl.compiler.types.TVar;
28 import org.simantics.scl.compiler.types.Type;
29 import org.simantics.scl.compiler.types.Types;
30
31 public final class SSAFunction implements Printable, BoundVarBinder {
32     Val target;
33     
34     TVar[] typeParameters;
35     Type effect;
36     SSABlock firstBlock;
37     SSABlock lastBlock;
38     ReturnCont returnCont;    
39     
40     FunctionBinder parent;
41     SSAFunction prev;
42     SSAFunction next;    
43     
44     public SSAFunction(TVar[] typeParameters, Type effect, Type returnType) {
45         this(typeParameters, effect, new ReturnCont(returnType));
46     }
47         
48     public SSAFunction(TVar[] typeParameters, Type effect, ReturnCont returnCont) {
49         this.typeParameters = typeParameters;
50         this.returnCont = returnCont;
51         this.effect = Types.canonical(effect);
52         returnCont.setParent(this);
53     }
54
55     public Val getTarget() {
56         return target;
57     }
58     
59     public void setTarget(Val target) {
60         this.target = target;
61         if(target instanceof BoundVar)
62             ((BoundVar) target).parent = this;             
63     }
64     
65     public void setTarget(BoundVar target) {
66         this.target = target;
67         target.parent = this;             
68     }
69     
70     public boolean hasEffect() {
71         return effect != Types.NO_EFFECTS;
72     }
73     
74     public void addBlock(SSABlock block) {
75         block.parent = this;
76         if(lastBlock == null) {
77             firstBlock = lastBlock = block;
78             block.next = block.prev = null;            
79         }
80         else {
81             lastBlock.next = block;
82             block.prev = lastBlock;
83             block.next = null;
84             lastBlock = block;
85         }
86     }
87     
88     public void addBlockInFront(SSABlock block) {
89         block.parent = this;
90         if(firstBlock == null) {
91             firstBlock = lastBlock = block;
92             block.next = block.prev = null;            
93         }
94         else {
95             firstBlock.prev = block;
96             block.next = firstBlock;
97             block.prev = null;
98             firstBlock = block;
99         }
100     }
101
102     public ReturnCont getReturnCont() {
103         return returnCont;
104     }
105     
106     public TVar[] getTypeParameters() {
107         return typeParameters;
108     }
109     
110     public SSABlock getFirstBlock() {
111         return firstBlock;
112     }
113     
114     public void generateCode(MethodBuilder mb) {
115         JavaTypeTranslator tt = mb.getJavaTypeTranslator();
116         for(int i=0,j=0;i<firstBlock.parameters.length;++i)
117             if(!tt.toTypeDesc(firstBlock.parameters[i].getType()).equals(TypeDesc.VOID))
118                 mb.setLocalVariable(firstBlock.parameters[i], mb.getParameter(j++));
119         for(SSABlock block = firstBlock; block != null; block = block.next)
120             block.prepare(mb);
121         firstBlock.generateCode(mb);
122     }
123
124     public void toString(PrintingContext context) {
125         context.indentation();
126         if(typeParameters.length > 0) {            
127             context.append('<');
128             boolean first = true;
129             for(TVar var : typeParameters) {
130                 if(first)
131                     first = false;
132                 else
133                     context.append(',');
134                 context.append(var);
135             }
136             context.append("> ");
137         }
138         if(hasEffect()) {
139             context.append(effect);
140             context.append(" ");
141         }
142         context.append("RETURNS ");
143         context.append(returnCont.getType());
144         context.append('\n');
145         
146         // Print blocks
147         context.pushBlockQueue();
148         context.addBlock(getFirstBlock());
149         while(true) {
150             SSABlock block = context.pollBlock();
151             if(block == null)
152                 break;
153             block.toString(context);
154         }
155         context.popBlockQueue();
156     }
157     
158     @Override
159     public String toString() {
160         PrintingContext context = new PrintingContext();
161         toString(context);
162         return context.toString();
163     }
164     
165     public void validate(SSAValidationContext context) {
166         if(target instanceof BoundVar && ((BoundVar)target).parent != this)
167             throw new InternalCompilerError();
168         
169         // Add valid type variables
170         for(TVar var : typeParameters)
171             context.validTypeVariables.add(var);
172         
173         // Add valid variables and continuations
174         context.validContinuations.add(returnCont);        
175         for(SSABlock block = firstBlock; block != null; block = block.next) {            
176             context.validContinuations.add(block);  
177             for(BoundVar parameter : block.parameters)
178                 context.validBoundVariables.add(parameter);
179             for(SSAStatement stat = block.firstStatement; stat != null; stat = stat.next)
180                 stat.addBoundVariablesTo(context);
181         }
182
183         // Validate blocks
184         for(SSABlock block = firstBlock; block != null; block = block.next)
185             block.validate(context);
186         context.validate(returnCont);
187         
188         //context.reset(); // FIXME not good when there are nested functions
189     }
190     
191     public void simplify(SSASimplificationContext context) {        
192         /*if(target instanceof BoundVar) {
193             tryToMakeMonadic(context);
194         }*/
195         for(SSABlock block = firstBlock; block != null; block = block.next)
196             block.simplify(context);
197         if(firstBlock == lastBlock && firstBlock.firstStatement == firstBlock.lastStatement &&
198                 firstBlock.firstStatement instanceof LetFunctions) {
199             simplifySingleLambda(context);            
200         }
201     }
202     
203     private void simplifySingleLambda(SSASimplificationContext context) {
204         LetFunctions letF = (LetFunctions)firstBlock.firstStatement;
205         SSAFunction f = letF.getFirstFunction();
206         if(f.getNext() != null)
207             return;
208         Val fVal = f.getTarget();
209         if(!firstBlock.exit.isJump(getReturnCont(), fVal))
210             return;
211         if(fVal.hasMoreThanOneOccurences())
212             return; // Possible if function is recursive and refers to itself
213         if(hasEffect())
214             return; // Not probably possible (?)
215                 
216         // Transform
217         for(SSABlock block = f.firstBlock; block != null; block = block.next)
218             block.parent = this;
219         lastBlock.next = f.firstBlock;
220         f.firstBlock.prev = lastBlock;        
221         lastBlock = f.lastBlock;
222         
223         firstBlock.firstStatement = firstBlock.lastStatement = null;
224         setReturnCont(f.getReturnCont());        
225         effect = f.effect;
226         BoundVar[] newParameters = BoundVar.copy(f.firstBlock.parameters);
227         firstBlock.setParameters(BoundVar.concat(getParameters(), newParameters));
228         firstBlock.setExit(new Jump(f.firstBlock.createOccurrence(), ValRef.createOccurrences(newParameters)));
229         context.markModified("SSAFunction.simplify-simple-lambda");
230     }
231
232     public void setReturnCont(ReturnCont returnCont) {
233         this.returnCont = returnCont;
234         returnCont.setParent(this);
235     }
236     
237     /*public void tryToMakeMonadic(SSASimplificationContext context) {
238         if(monadic)
239             return;
240         if(!Types.isApply(BTypes.PROC, 1, getReturnType()))
241             return;        
242         for(ValRef ref = target.getOccurrence(); ref != null; ref = ref.getNext()) {
243             ValRefBinder parent = ref.getParent();
244             if(!(parent instanceof LetApply))
245                 return;
246             LetApply apply = (LetApply)parent;
247             if(apply.getFunction() != ref)
248                 return;
249             if(apply.getParameters().length != getParameters().length)
250                 return;
251             if(!apply.hasEffect())
252                 return;
253         }        
254         makeMonadic(context);
255     }*/
256     
257     /*private void makeMonadic(SSASimplificationContext context) {
258         Type oldReturnType = returnCont.getType();
259         Type newReturnType;
260         try {
261             newReturnType = Types.matchApply(BTypes.PROC, oldReturnType);
262         } catch (MatchException e) {
263             throw new InternalCompilerError();
264         }
265         
266         //
267         returnCont.setType(newReturnType);
268         monadic = true;
269         
270         //
271         SSABlock block = new SSABlock(oldReturnType);
272         addBlock(block);
273         
274         returnCont.replaceWith(block);
275         
276         BoundVar x = new BoundVar(newReturnType);
277         LetApply apply = new LetApply(x, block.parameters[0].createOccurrence());
278         apply.setMonadic(true);
279         block.addStatement(apply);
280         
281         block.setExit(new Jump(returnCont.createOccurrence(), x.createOccurrence()));
282         context.markModified("SSAFunction.make-monadic");
283     }*/
284
285     public ValRef isEqualToConstant() {
286         if(firstBlock.parameters.length > 0)
287             return null;
288         if(firstBlock != lastBlock)
289             return null;
290         if(firstBlock.firstStatement != null)
291             return null;
292         if(!(firstBlock.exit instanceof Jump))
293             return null;
294         Jump exit = (Jump)firstBlock.exit;
295         if(exit.getTarget().getBinding() != returnCont)
296             return null;
297         return exit.getParameters()[0];
298     }    
299
300     public BoundVar[] getParameters() {
301         return firstBlock.parameters;                
302     }
303     
304     public Type[] getParameterTypes() {
305         return Types.getTypes(firstBlock.parameters);                
306     }
307
308     public int getArity() {
309         return firstBlock.parameters.length;
310     }
311
312     public void markGenerateOnFly() {
313         for(SSABlock block = firstBlock; block != null; block = block.next)
314             block.markGenerateOnFly();
315     }
316
317     public SSAFunction copy(CopyContext context) {
318         TVar[] newTypeParameters = context.copyParameters(typeParameters);
319         SSAFunction newFunction = new SSAFunction(newTypeParameters, effect, context.copy(returnCont));
320         for(SSABlock block = firstBlock;
321                 block != null; block = block.next)
322             newFunction.addBlock(context.copy(block));
323         return newFunction;
324     }
325
326     public SSAFunction copy() {
327         return copy(new CopyContext());
328     }
329
330     public void replace(TVar[] vars, Type[] replacements) {
331         returnCont.replace(vars, replacements);
332         for(SSABlock block = firstBlock;
333                 block != null; block = block.next)
334             block.replace(vars, replacements);
335     }
336
337     public void setTypeParameters(TVar[] typeParameters) {
338         this.typeParameters = typeParameters;
339     }
340
341     public Type getType() {
342         Type type = returnCont.getType();
343         type = Types.functionE(
344                 Types.getTypes(firstBlock.parameters),
345                 effect,
346                 type);
347         type = Types.forAll(typeParameters, type);
348         return type;
349     }
350
351     public void mergeBlocks(SSAFunction function) {
352         SSABlock block = function.firstBlock;
353         while(block != null) {
354             SSABlock next = block.next;
355             addBlock(block);
356             block = next;
357         }
358     }
359
360     public Type getReturnType() {
361         return returnCont.getType();
362     }
363
364     public void destroy() {
365         for(SSABlock block = firstBlock;
366                 block != null; block = block.next)
367             block.destroy();
368     }
369     
370     public void detach() {
371         if(prev == null)
372             parent.setFirstFunction(next);
373         else
374             prev.next = next;
375         if(next != null)
376             next.prev = prev;
377     }
378     
379     public void remove() {
380         destroy();
381         detach();
382     }
383     
384     public void addSibling(SSAFunction function) {
385         function.parent = parent;
386         function.next = next;
387         function.prev = this;
388         
389         next.prev = function;
390         next = function;
391     }
392
393     public SSAFunction getNext() {
394         return next;
395     }
396
397     public void setParent(FunctionBinder parent) {
398         this.parent = parent;
399     }
400
401     public void setPrev(SSAFunction function) {
402         this.prev = function;
403     }
404
405     public void setNext(SSAFunction function) {
406         this.next = function;
407     }
408     
409     public void collectFreeVariables(ArrayList<ValRef> vars) {
410         for(SSABlock block = firstBlock;
411                 block != null; block = block.next)
412             block.collectFreeVariables(this, vars);
413     }
414
415     @Override
416     public SSAFunction getParentFunction() {
417         return parent.getParentFunction();
418     }
419     
420     public FunctionBinder getParent() {
421         return parent;
422     }
423     
424     public void lambdaLift(SSALambdaLiftingContext context) {
425         for(SSABlock block = firstBlock;
426                 block != null; block = block.next)
427             block.lambdaLift(context);
428     }
429
430     public void addParametersInFront(BoundVar[] parameters) {
431         Cont proxy = null;
432         for(ContRef ref = firstBlock.getOccurrence(); ref != null; ref = ref.getNext())
433             proxy = ref.addParametersInFront(parameters, firstBlock.parameters, proxy);
434         
435         firstBlock.parameters = BoundVar.concat(parameters, firstBlock.parameters);
436         for(BoundVar parameter : parameters)
437             parameter.parent = firstBlock;
438     }
439     
440     public void apply(ValRef[] parameters) {
441         if(parameters.length == 0)
442             return;
443         if(firstBlock.hasNoOccurences()) {
444             BoundVar[] vars = firstBlock.getParameters();
445             for(int i=0;i<parameters.length;++i)
446                 vars[i].replaceBy(parameters[i]);
447             firstBlock.setParameters(Arrays.copyOfRange(vars, parameters.length, vars.length));
448         }
449         else {
450             BoundVar[] newVars = new BoundVar[getArity()-parameters.length];
451             SSABlock block = new SSABlock(newVars);
452             block.setExit(new Jump(firstBlock.createOccurrence(), 
453                     ValRef.concat(ValRef.copy(parameters), ValRef.createOccurrences(newVars))));
454             addBlockInFront(block);
455         }
456     }
457
458     public void applyTypes(Type[] types) {
459         if(types.length == 0)
460             return;
461         if(types.length == typeParameters.length) {
462             replace(typeParameters, types);
463             typeParameters = TVar.EMPTY_ARRAY;
464         }
465         else {
466             replace(Arrays.copyOf(typeParameters, types.length), types);
467             typeParameters = 
468                     Arrays.copyOfRange(typeParameters, 
469                             types.length, typeParameters.length);
470         }            
471     }
472     
473     public boolean isSimpleEnoughForInline() {
474         return firstBlock == lastBlock && 
475                 (firstBlock.firstStatement == null || 
476                 (firstBlock.firstStatement == firstBlock.lastStatement
477                 && firstBlock.firstStatement instanceof LetApply));
478     }
479
480     public Type getEffect() {
481         return effect;
482     }
483
484     public int getBlockCount() {
485         int count = 0;
486         for(SSABlock block = firstBlock;block != null;block = block.next)
487             ++count;
488         return count;
489     }
490
491 }