gerrit.simantics Code Review - simantics/platform.git/blob

   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(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 }