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