(refs #7250) Merging master, minor CHR bugfixes
[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / internal / codegen / ssa / statements / LetApply.java
1 package org.simantics.scl.compiler.internal.codegen.ssa.statements;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5
6 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
7 import org.simantics.scl.compiler.constants.Constant;
8 import org.simantics.scl.compiler.constants.SCLConstant;
9 import org.simantics.scl.compiler.internal.codegen.continuations.ContRef;
10 import org.simantics.scl.compiler.internal.codegen.references.BoundVar;
11 import org.simantics.scl.compiler.internal.codegen.references.Val;
12 import org.simantics.scl.compiler.internal.codegen.references.ValRef;
13 import org.simantics.scl.compiler.internal.codegen.ssa.SSABlock;
14 import org.simantics.scl.compiler.internal.codegen.ssa.SSAExit;
15 import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;
16 import org.simantics.scl.compiler.internal.codegen.ssa.SSAStatement;
17 import org.simantics.scl.compiler.internal.codegen.ssa.binders.BoundVarBinder;
18 import org.simantics.scl.compiler.internal.codegen.ssa.binders.ValRefBinder;
19 import org.simantics.scl.compiler.internal.codegen.ssa.exits.Jump;
20 import org.simantics.scl.compiler.internal.codegen.ssa.exits.Switch;
21 import org.simantics.scl.compiler.internal.codegen.utils.CopyContext;
22 import org.simantics.scl.compiler.internal.codegen.utils.MethodBuilder;
23 import org.simantics.scl.compiler.internal.codegen.utils.PrintingContext;
24 import org.simantics.scl.compiler.internal.codegen.utils.SSASimplificationContext;
25 import org.simantics.scl.compiler.internal.codegen.utils.SSAValidationContext;
26 import org.simantics.scl.compiler.internal.codegen.utils.ValRefVisitor;
27 import org.simantics.scl.compiler.top.SCLCompilerConfiguration;
28 import org.simantics.scl.compiler.types.TVar;
29 import org.simantics.scl.compiler.types.Type;
30 import org.simantics.scl.compiler.types.Types;
31 import org.simantics.scl.compiler.types.exceptions.MatchException;
32 import org.simantics.scl.compiler.types.util.MultiFunction;
33
34 public class LetApply extends LetStatement implements ValRefBinder {
35     private ValRef function;
36     private ValRef[] parameters;
37     Type effect;
38     
39     public LetApply(BoundVar target, Type effect, ValRef function, ValRef ... parameters) {
40         super(target);
41         if(SCLCompilerConfiguration.DEBUG) {
42             if(effect == null)
43                 throw new InternalCompilerError();
44             if(function.getBinding() == null)
45                 throw new InternalCompilerError();
46         }
47         this.setFunction(function);
48         this.setParameters(parameters);
49         this.effect = Types.canonical(effect);
50     }
51
52     public void push(MethodBuilder mb) {
53         //mb.getCodeBuilder().mapLineNumber(lineNumber);
54         Val f = getFunction().getBinding();
55         Val[] ps = ValRef.getBindings(getParameters());
56         if(f instanceof Constant) {
57             Constant cf = (Constant)f;
58             Type returnType = cf.apply(mb, getFunction().getTypeParameters(), ps);
59             if(Types.isBoxed(returnType))
60                 mb.unbox(target.getType());
61         }
62         else {            
63             mb.push(f, f.getType());
64             mb.pushBoxed(ps);
65             mb.genericApply(ps.length);
66             mb.unbox(target.getType());
67         }
68     }
69     
70     @Override
71     public void generateCode(MethodBuilder mb) {
72         if(!target.generateOnFly) {
73             push(mb);
74             mb.store(target);
75         }
76     }
77
78     @Override
79     public void toString(PrintingContext context) {
80         if(/*target.getLabel() == null &&*/ determineGenerateOnFly())
81             context.addInlineExpression(target, this);
82         else
83             toStringAux(context);
84     }
85     
86     private void toStringAux(PrintingContext context) {
87         context.indentation();
88         context.append(target);
89         context.append("(" + target.occurrenceCount() + ")");
90         context.append(" = ");
91         bodyToString(context);
92         context.append('\n');
93         
94     }
95     
96     public void bodyToString(PrintingContext context) {
97         if(context.getErrorMarker() == this)
98             context.append("!> ");
99         if(hasEffect()) {
100             context.append("<");
101             context.append(effect);
102             context.append("> ");
103         }
104         context.append(getFunction());
105         for(ValRef parameter : getParameters()) {
106             context.append(' ');
107             context.append(parameter);
108         }
109     }
110     
111     @Override
112     public String toString() {
113         PrintingContext context = new PrintingContext();
114         toStringAux(context);
115         return context.toString();
116     }
117
118     @Override
119     public void validate(SSAValidationContext context) {
120         context.validate(target);
121         if(target.getParent() != this)
122             throw new InternalCompilerError();
123         context.validate(function);
124         if(function.getParent() != this)
125             throw new InternalCompilerError();
126         for(ValRef parameter : parameters) {
127             context.validate(parameter);
128             if(parameter.getParent() != this)
129                 throw new InternalCompilerError();
130         }
131         //if(parameters.length == 0)
132         //    throw new InternalCompilerError();
133         
134         
135         MultiFunction mFun;
136         try {
137             mFun = Types.matchFunction(getFunction().getType(), getParameters().length);
138         } catch (MatchException e) {
139             context.setErrorMarker(this);
140             throw new InternalCompilerError();
141         }
142         for(int i=0;i<getParameters().length;++i)
143             context.assertSubsumes(this, getParameters()[i].getType(), mFun.parameterTypes[i]);
144         context.assertSubsumes(this, target.getType(), mFun.returnType);
145         context.assertEqualsEffect(this, effect, mFun.effect);
146     }
147
148     @Override
149     public void destroy() {
150         getFunction().remove();
151         for(ValRef parameter : getParameters())
152             parameter.remove();
153     }
154     
155     @Override
156     public void simplify(SSASimplificationContext context) {
157         if(target.hasNoOccurences() && !hasEffect()) {
158             remove();
159             context.markModified("LetApply.dead-let-statement");
160             return;
161         }
162         // TODO this is quite heavy way for inlining constants
163         for(int i=0;i<parameters.length;++i) {
164             ValRef parameter = parameters[i];
165             Val value = parameter.getBinding();
166             if(!(value instanceof SCLConstant))
167                 continue;
168             SCLConstant constant = (SCLConstant)value;
169             if(constant.inlineArity != 0)
170                 continue;
171             SSAFunction definition = constant.definition;
172             SSABlock block = definition.getFirstBlock();
173             if(block.getFirstStatement() != null || !(block.getExit() instanceof Jump))
174                 continue;
175             Jump jump = (Jump)block.getExit();
176             if(jump.getTarget().getBinding() != definition.getReturnCont())
177                 continue;
178             if(jump.getParameter(0).getTypeParameters().length > 0)
179                 continue;
180             parameter.replaceBy(jump.getParameter(0).getBinding());
181         }
182         Val functionVal = getFunction().getBinding();
183         if(functionVal instanceof BoundVar) {
184             BoundVarBinder parent_ = ((BoundVar)functionVal).parent;
185             if(parent_ instanceof SSAFunction) {
186                 SSAFunction function = (SSAFunction)parent_;
187                 if(functionVal.hasMoreThanOneOccurences())
188                     return;
189                 if(getParameters().length < function.getArity())
190                     return;
191                 if(getParameters().length > function.getArity())
192                     split(function.getArity());
193                 inline(function);
194                 function.detach();
195                 context.markModified("LetApply.beta-lambda");
196             }
197             else if(parent_ instanceof LetApply) {
198                 LetApply apply = (LetApply)parent_;
199                 if(apply.hasEffect())
200                     return;
201                 boolean hasJustOneOccurence = !functionVal.hasMoreThanOneOccurences();
202                 if((hasJustOneOccurence && apply.getParent() == getParent()) ||
203                         apply.isPartial()) {
204                     if(hasJustOneOccurence) {
205                         apply.detach();
206                         setFunction(apply.getFunction());
207                         setParameters(ValRef.concat(apply.getParameters(), getParameters()));
208                     }
209                     else {
210                         setFunction(apply.getFunction().copy());
211                         setParameters(ValRef.concat(ValRef.copy(apply.getParameters()), getParameters()));
212                     }
213                     context.markModified("LetApply.merge-applications");
214                 }
215             }
216             else if(parent_ instanceof SSABlock) {
217                 SSABlock parent = getParent();
218                 if(parent_ != parent)
219                     return;
220                 if(parent.getFirstStatement() != this)
221                     return;
222                 if(!parent.hasMoreThanOneOccurences())
223                     return; // We stop here, because situation can be handled by better transformations
224                 if(functionVal.hasMoreThanOneOccurences())
225                     return;
226                 // We have now the following situation:
227                 //    [c] ... f ... =
228                 //        x = f ... 
229                 // * this application is the only reference to f
230                 // * there are multiple references to [c]
231                 for(ContRef ref = parent.getOccurrence();ref != null; ref = ref.getNext())
232                     if(!(ref.getParent() instanceof Jump))
233                         return;
234                 
235                 // Finds the position of the functionVal in the parameter list of 
236                 // the parent block.
237                 int position;
238                 for(position=0;position<parent.getParameters().length;++position)
239                     if(parent.getParameters()[position] == functionVal)
240                         break;
241                 if(position == parent.getParameters().length)
242                     throw new InternalCompilerError();
243                 
244                 // Do tranformation
245                 for(ContRef ref = parent.getOccurrence();ref != null; ref = ref.getNext()) {
246                     Jump jump = (Jump)ref.getParent();
247                     SSABlock block = jump.getParent();
248                     
249                     BoundVar newTarget = new BoundVar(target.getType());
250                     block.addStatement(new LetApply(newTarget, effect, jump.getParameter(position), ValRef.copy(parameters)));
251                     jump.setParameter(position, newTarget.createOccurrence());
252                 }
253                 
254                 parent.setParameter(position, target);
255                 remove();
256                 context.markModified("LetApply.hoist-apply");
257             }
258         }
259         else if(functionVal instanceof Constant) {
260             ((Constant)functionVal).inline(context, this);
261         }
262     }
263     
264     public boolean isPartial() {
265         return parameters.length < function.getBinding().getEffectiveArity();
266     }
267
268     /**
269      * Removes apply if it does not have parameters.
270      */
271     public void removeDegenerated() {
272         if(getParameters().length == 0) {
273             target.replaceBy(getFunction());
274             getFunction().remove();
275             detach();
276         }
277     }
278
279     public boolean determineGenerateOnFly() {
280         if(hasEffect())
281             return false;
282         ValRef ref = target.getOccurrence();
283         if(ref == null || ref.getNext() != null)
284             return false;
285         Object parent = ref.getParent();
286         if(parent instanceof SSAStatement) {
287             if(((SSAStatement)parent).getParent() != getParent())
288                 return false;
289         }
290         else if(parent instanceof SSAExit) {
291             if(((SSAExit)parent).getParent() != getParent())
292                 return false;
293             if(parent instanceof Switch)
294                 return false;
295         }
296         else
297             return false;
298         return true;
299     }
300     
301     @Override
302     public void markGenerateOnFly() {        
303         target.generateOnFly = determineGenerateOnFly();
304     }
305
306     public ValRef getFunction() {
307         return function;
308     }
309
310     public void setFunction(ValRef function) {
311         this.function = function;
312         function.setParent(this);
313     }
314
315     public ValRef[] getParameters() {
316         return parameters;
317     }
318
319     public void setParameters(ValRef[] parameters) {
320         /*if(SCLCompilerConfiguration.DEBUG)
321             if(parameters.length == 0)
322                 throw new InternalCompilerError();*/
323         this.parameters = parameters;
324         for(ValRef parameter : parameters)
325             parameter.setParent(this);
326     }
327     
328     @Override
329     public SSAStatement copy(CopyContext context) {
330         LetApply result = new LetApply(context.copy(target), 
331                 context.copyType(effect),
332                 context.copy(function), 
333                 context.copy(parameters));
334         return result;
335     }
336     
337     @Override
338     public void replace(TVar[] vars, Type[] replacements) {
339         target.replace(vars, replacements);
340         function.replace(vars, replacements);
341         effect = effect.replace(vars, replacements);
342         for(ValRef parameter : parameters)
343             parameter.replace(vars, replacements);
344     }
345     
346     /**
347      * Inlines the application by the given function.
348      * It is assumed that the function has the same number
349      * of parameters as this one and there are no other 
350      * references to the function (copy function before
351      * inlining if necessary).
352      */
353     public void inline(SSAFunction function) {
354         if(function.getArity() != parameters.length)
355             throw new InternalCompilerError();        
356                
357         SSABlock headBlock = getParent();
358         SSAFunction thisFunction = headBlock.getParent();
359                
360         /*System.out.println("--- INLINING -------------------------------");
361         System.out.println(thisFunction);
362         System.out.println("Function name: " + getFunction().getBinding());
363         System.out.println("++++++++++++++++++++++++++++++++++++++++++++");
364         System.out.println(function);   
365         */
366         
367         if(this.function.getTypeParameters().length > 0) {
368             /*if(function.getParent() != null) {
369                 PrintingContext pc = new PrintingContext();
370                 pc.append("----------------------------\n");
371                 function.getParent().getParentFunction().toString(pc);
372                 pc.append("\n----\n");
373                 function.toString(pc);
374                 pc.append("\n");
375                 pc.append(function.getTypeParameters());
376                 pc.append(" -> ");
377                 pc.append(this.function.getTypeParameters());
378                 System.out.println(pc.toString());
379             }*/
380             function.replace(function.getTypeParameters(), this.function.getTypeParameters());
381         }
382
383         if(getPrev() != null)
384             getPrev().setAsLastStatement();
385         else
386             headBlock.removeStatements();
387         
388         // Create tail block
389         SSABlock tailBlock = new SSABlock(new BoundVar[] {target});
390         thisFunction.addBlock(tailBlock);
391         {
392             SSAStatement stat = getNext();
393             while(stat != null) {
394                 SSAStatement temp = stat.getNext();
395                 tailBlock.addStatement(stat);
396                 stat = temp;
397             }
398         }
399         tailBlock.setExit(headBlock.getExit());
400         
401         // Merge blocks        
402         thisFunction.mergeBlocks(function);
403         
404         headBlock.setExit(new Jump(function.getFirstBlock().createOccurrence(), 
405                 parameters));
406         function.getReturnCont().replaceWith(tailBlock);
407
408         this.function.remove();
409         // Note: No need to remove or detach this statement anymore
410         
411         // TODO remove function
412         /*
413         System.out.println("============================================");
414         System.out.println(thisFunction);
415         */
416     }
417
418     @Override
419     public void collectFreeVariables(SSAFunction parentFunction,
420             ArrayList<ValRef> vars) {
421         function.collectFreeVariables(parentFunction, vars);
422         for(ValRef parameter : parameters)
423             parameter.collectFreeVariables(parentFunction, vars);
424     }
425     
426     @Override
427     public void replaceByApply(ValRef valRef, Val newFunction, Type[] typeParameters, Val[] parameters) {
428         if(function == valRef) {
429             valRef.remove();
430             setFunction(newFunction.createOccurrence(typeParameters));
431             setParameters(ValRef.concat(ValRef.createOccurrences(parameters), this.parameters));
432         }
433         else
434             super.replaceByApply(valRef, newFunction, typeParameters, parameters);
435     }
436
437     /**
438      * Splits this application into two applications where the first has
439      * the arity given as a parameter and the new application inserted 
440      * after this statement has the rest of the parameters.
441      */
442     public void split(int arity) {
443         if(arity == parameters.length)
444             return;
445         if(arity > parameters.length)
446             throw new InternalCompilerError();
447         ValRef[] firstHalf = arity == 0 ? ValRef.EMPTY_ARRAY : Arrays.copyOf(parameters, arity);
448         ValRef[] secondHalf = arity == parameters.length ? ValRef.EMPTY_ARRAY : Arrays.copyOfRange(parameters, arity, parameters.length);
449         BoundVar newVar;
450         try {
451             MultiFunction mfun = Types.matchFunction(function.getType(), arity);
452             newVar = new BoundVar(mfun.returnType);
453         } catch (MatchException e) {
454             throw new InternalCompilerError();
455         }
456         LetApply newApply = new LetApply(target, effect, 
457                 newVar.createOccurrence(), secondHalf);
458         newApply.insertAfter(this);
459         effect = Types.NO_EFFECTS;
460         setTarget(newVar);
461         setParameters(firstHalf);
462     }
463     
464     /**
465      * True, if the application may have side effects.
466      */
467     public boolean hasEffect() {
468         return effect != Types.NO_EFFECTS;
469     }
470
471     public void updateEffect() {
472         try {
473             MultiFunction mFun = Types.matchFunction(function.getType(), parameters.length);
474             this.effect = mFun.effect;
475         } catch (MatchException e) {
476             throw new InternalCompilerError(e);
477         }
478     }
479     
480     @Override
481     public void prepare(MethodBuilder mb) {
482         function.getBinding().prepare(mb);
483     }
484
485     @Override
486     public void forValRefs(ValRefVisitor visitor) {
487         visitor.visit(function);
488         for(ValRef parameter : parameters)
489             visitor.visit(parameter);
490     }
491 }