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