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         if(thisFunction == function)
 360             return;
 361
 362         /*System.out.println("--- INLINING -------------------------------");
 363         System.out.println(thisFunction);
 364         System.out.println("Function name: " + getFunction().getBinding());
 365         System.out.println("++++++++++++++++++++++++++++++++++++++++++++");
 366         System.out.println(function);
 367         */
 368
 369         if(this.function.getTypeParameters().length > 0) {
 370             /*if(function.getParent() != null) {
 371                 PrintingContext pc = new PrintingContext();
 372                 pc.append("----------------------------\n");
 373                 function.getParent().getParentFunction().toString(pc);
 374                 pc.append("\n----\n");
 375                 function.toString(pc);
 376                 pc.append("\n");
 377                 pc.append(function.getTypeParameters());
 378                 pc.append(" -> ");
 379                 pc.append(this.function.getTypeParameters());
 380                 System.out.println(pc.toString());
 381             }*/
 382             function.replace(function.getTypeParameters(), this.function.getTypeParameters());
 383         }
 384
 385         if(getPrev() != null)
 386             getPrev().setAsLastStatement();
 387         else
 388             headBlock.removeStatements();
 389
 390         // Create tail block
 391         SSABlock tailBlock = new SSABlock(new BoundVar[] {target});
 392         thisFunction.addBlock(tailBlock);
 393         {
 394             SSAStatement stat = getNext();
 395             while(stat != null) {
 396                 SSAStatement temp = stat.getNext();
 397                 tailBlock.addStatement(stat);
 398                 stat = temp;
 399             }
 400         }
 401         tailBlock.setExit(headBlock.getExit());
 402
 403         // Merge blocks
 404         thisFunction.mergeBlocks(function);
 405
 406         headBlock.setExit(new Jump(function.getFirstBlock().createOccurrence(),
 407                 parameters));
 408         function.getReturnCont().replaceWith(tailBlock);
 409
 410         this.function.remove();
 411         // Note: No need to remove or detach this statement anymore
 412
 413         // TODO remove function
 414         /*
 415         System.out.println("============================================");
 416         System.out.println(thisFunction);
 417         */
 418     }
 419
 420     @Override
 421     public void collectFreeVariables(SSAFunction parentFunction,
 422             ArrayList<ValRef> vars) {
 423         function.collectFreeVariables(parentFunction, vars);
 424         for(ValRef parameter : parameters)
 425             parameter.collectFreeVariables(parentFunction, vars);
 426     }
 427
 428     @Override
 429     public void replaceByApply(ValRef valRef, Val newFunction, Type[] typeParameters, Val[] parameters) {
 430         if(function == valRef) {
 431             valRef.remove();
 432             setFunction(newFunction.createOccurrence(typeParameters));
 433             setParameters(ValRef.concat(ValRef.createOccurrences(parameters), this.parameters));
 434         }
 435         else
 436             super.replaceByApply(valRef, newFunction, typeParameters, parameters);
 437     }
 438
 439     /**
 440      * Splits this application into two applications where the first has
 441      * the arity given as a parameter and the new application inserted
 442      * after this statement has the rest of the parameters.
 443      */
 444     public void split(int arity) {
 445         if(arity == parameters.length)
 446             return;
 447         if(arity > parameters.length)
 448             throw new InternalCompilerError();
 449         ValRef[] firstHalf = arity == 0 ? ValRef.EMPTY_ARRAY : Arrays.copyOf(parameters, arity);
 450         ValRef[] secondHalf = arity == parameters.length ? ValRef.EMPTY_ARRAY : Arrays.copyOfRange(parameters, arity, parameters.length);
 451         BoundVar newVar;
 452         try {
 453             MultiFunction mfun = Types.matchFunction(function.getType(), arity);
 454             newVar = new BoundVar(mfun.returnType);
 455         } catch (MatchException e) {
 456             throw new InternalCompilerError();
 457         }
 458         LetApply newApply = new LetApply(target, effect,
 459                 newVar.createOccurrence(), secondHalf);
 460         newApply.insertAfter(this);
 461         effect = Types.NO_EFFECTS;
 462         setTarget(newVar);
 463         setParameters(firstHalf);
 464     }
 465
 466     /**
 467      * True, if the application may have side effects.
 468      */
 469     public boolean hasEffect() {
 470         return effect != Types.NO_EFFECTS;
 471     }
 472
 473     public void updateEffect() {
 474         try {
 475             MultiFunction mFun = Types.matchFunction(function.getType(), parameters.length);
 476             this.effect = mFun.effect;
 477         } catch (MatchException e) {
 478             throw new InternalCompilerError(e);
 479         }
 480     }
 481
 482     @Override
 483     public void prepare(MethodBuilder mb) {
 484         function.getBinding().prepare(mb);
 485     }
 486
 487     @Override
 488     public void forValRefs(ValRefVisitor visitor) {
 489         visitor.visit(function);
 490         for(ValRef parameter : parameters)
 491             visitor.visit(parameter);
 492     }
 493
 494     @Override
 495     public void cleanup() {
 496         function.remove();
 497         for(ValRef parameter : parameters)
 498             parameter.remove();
 499     }
 500 }