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