bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/SSAFunction.java

   1 package org.simantics.scl.compiler.internal.codegen.ssa;
   2
   3 import java.util.ArrayList;
   4 import java.util.Arrays;
   5
   6 import org.cojen.classfile.TypeDesc;
   7 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
   8 import org.simantics.scl.compiler.internal.codegen.continuations.Cont;
   9 import org.simantics.scl.compiler.internal.codegen.continuations.ContRef;
  10 import org.simantics.scl.compiler.internal.codegen.continuations.ReturnCont;
  11 import org.simantics.scl.compiler.internal.codegen.references.BoundVar;
  12 import org.simantics.scl.compiler.internal.codegen.references.Val;
  13 import org.simantics.scl.compiler.internal.codegen.references.ValRef;
  14 import org.simantics.scl.compiler.internal.codegen.ssa.binders.BoundVarBinder;
  15 import org.simantics.scl.compiler.internal.codegen.ssa.binders.FunctionBinder;
  16 import org.simantics.scl.compiler.internal.codegen.ssa.exits.Jump;
  17 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;
  18 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetFunctions;
  19 import org.simantics.scl.compiler.internal.codegen.types.JavaTypeTranslator;
  20 import org.simantics.scl.compiler.internal.codegen.utils.CopyContext;
  21 import org.simantics.scl.compiler.internal.codegen.utils.MethodBuilder;
  22 import org.simantics.scl.compiler.internal.codegen.utils.Printable;
  23 import org.simantics.scl.compiler.internal.codegen.utils.PrintingContext;
  24 import org.simantics.scl.compiler.internal.codegen.utils.SSALambdaLiftingContext;
  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.types.TVar;
  28 import org.simantics.scl.compiler.types.Type;
  29 import org.simantics.scl.compiler.types.Types;
  30
  31 public final class SSAFunction implements Printable, BoundVarBinder {
  32     Val target;
  33
  34     TVar[] typeParameters;
  35     Type effect;
  36     SSABlock firstBlock;
  37     SSABlock lastBlock;
  38     ReturnCont returnCont;
  39
  40     FunctionBinder parent;
  41     SSAFunction prev;
  42     SSAFunction next;
  43
  44     public SSAFunction(TVar[] typeParameters, Type effect, Type returnType) {
  45         this(typeParameters, effect, new ReturnCont(returnType));
  46     }
  47
  48     public SSAFunction(TVar[] typeParameters, Type effect, ReturnCont returnCont) {
  49         this.typeParameters = typeParameters;
  50         this.returnCont = returnCont;
  51         this.effect = Types.canonical(effect);
  52         returnCont.setParent(this);
  53     }
  54
  55     public Val getTarget() {
  56         return target;
  57     }
  58
  59     public void setTarget(Val target) {
  60         this.target = target;
  61         if(target instanceof BoundVar)
  62             ((BoundVar) target).parent = this;
  63     }
  64
  65     public void setTarget(BoundVar target) {
  66         this.target = target;
  67         target.parent = this;
  68     }
  69
  70     public boolean hasEffect() {
  71         return effect != Types.NO_EFFECTS;
  72     }
  73
  74     public void addBlock(SSABlock block) {
  75         block.parent = this;
  76         if(lastBlock == null) {
  77             firstBlock = lastBlock = block;
  78             block.next = block.prev = null;
  79         }
  80         else {
  81             lastBlock.next = block;
  82             block.prev = lastBlock;
  83             block.next = null;
  84             lastBlock = block;
  85         }
  86     }
  87
  88     public void addBlockInFront(SSABlock block) {
  89         block.parent = this;
  90         if(firstBlock == null) {
  91             firstBlock = lastBlock = block;
  92             block.next = block.prev = null;
  93         }
  94         else {
  95             firstBlock.prev = block;
  96             block.next = firstBlock;
  97             block.prev = null;
  98             firstBlock = block;
  99         }
 100     }
 101
 102     public ReturnCont getReturnCont() {
 103         return returnCont;
 104     }
 105
 106     public TVar[] getTypeParameters() {
 107         return typeParameters;
 108     }
 109
 110     public SSABlock getFirstBlock() {
 111         return firstBlock;
 112     }
 113
 114     public void generateCode(MethodBuilder mb) {
 115         JavaTypeTranslator tt = mb.getJavaTypeTranslator();
 116         for(int i=0,j=0;i<firstBlock.parameters.length;++i)
 117             if(!tt.toTypeDesc(firstBlock.parameters[i].getType()).equals(TypeDesc.VOID))
 118                 mb.setLocalVariable(firstBlock.parameters[i], mb.getParameter(j++));
 119         for(SSABlock block = firstBlock; block != null; block = block.next)
 120             block.prepare(mb);
 121         firstBlock.generateCode(mb);
 122     }
 123
 124     public void toString(PrintingContext context) {
 125         context.indentation();
 126         if(typeParameters.length > 0) {
 127             context.append('<');
 128             boolean first = true;
 129             for(TVar var : typeParameters) {
 130                 if(first)
 131                     first = false;
 132                 else
 133                     context.append(',');
 134                 context.append(var);
 135             }
 136             context.append("> ");
 137         }
 138         if(hasEffect()) {
 139             context.append(effect);
 140             context.append(" ");
 141         }
 142         context.append("RETURNS ");
 143         context.append(returnCont.getType());
 144         context.append('\n');
 145
 146         // Print blocks
 147         context.pushBlockQueue();
 148         context.addBlock(getFirstBlock());
 149         while(true) {
 150             SSABlock block = context.pollBlock();
 151             if(block == null)
 152                 break;
 153             block.toString(context);
 154         }
 155         context.popBlockQueue();
 156     }
 157
 158     @Override
 159     public String toString() {
 160         PrintingContext context = new PrintingContext();
 161         toString(context);
 162         return context.toString();
 163     }
 164
 165     public void validate(SSAValidationContext context) {
 166         if(target instanceof BoundVar && ((BoundVar)target).parent != this)
 167             throw new InternalCompilerError();
 168
 169         // Add valid type variables
 170         for(TVar var : typeParameters)
 171             context.validTypeVariables.add(var);
 172
 173         // Add valid variables and continuations
 174         context.validContinuations.add(returnCont);
 175         for(SSABlock block = firstBlock; block != null; block = block.next) {
 176             context.validContinuations.add(block);
 177             for(BoundVar parameter : block.parameters)
 178                 context.validBoundVariables.add(parameter);
 179             for(SSAStatement stat = block.firstStatement; stat != null; stat = stat.next)
 180                 stat.addBoundVariablesTo(context);
 181         }
 182
 183         // Validate blocks
 184         for(SSABlock block = firstBlock; block != null; block = block.next)
 185             block.validate(context);
 186         context.validate(returnCont);
 187
 188         //context.reset(); // FIXME not good when there are nested functions
 189     }
 190
 191     public void simplify(SSASimplificationContext context) {
 192         /*if(target instanceof BoundVar) {
 193             tryToMakeMonadic(context);
 194         }*/
 195         for(SSABlock block = firstBlock; block != null; block = block.next)
 196             block.simplify(context);
 197         if(firstBlock == lastBlock && firstBlock.firstStatement == firstBlock.lastStatement &&
 198                 firstBlock.firstStatement instanceof LetFunctions) {
 199             simplifySingleLambda(context);
 200         }
 201     }
 202
 203     private void simplifySingleLambda(SSASimplificationContext context) {
 204         LetFunctions letF = (LetFunctions)firstBlock.firstStatement;
 205         SSAFunction f = letF.getFirstFunction();
 206         if(f.getNext() != null)
 207             return;
 208         Val fVal = f.getTarget();
 209         if(!firstBlock.exit.isJump(getReturnCont(), fVal))
 210             return;
 211         if(fVal.hasMoreThanOneOccurences())
 212             return; // Possible if function is recursive and refers to itself
 213         if(hasEffect())
 214             return; // Not probably possible (?)
 215
 216         // Transform
 217         for(SSABlock block = f.firstBlock; block != null; block = block.next)
 218             block.parent = this;
 219         lastBlock.next = f.firstBlock;
 220         f.firstBlock.prev = lastBlock;
 221         lastBlock = f.lastBlock;
 222
 223         firstBlock.firstStatement = firstBlock.lastStatement = null;
 224         setReturnCont(f.getReturnCont());
 225         effect = f.effect;
 226         BoundVar[] newParameters = BoundVar.copy(f.firstBlock.parameters);
 227         firstBlock.setParameters(BoundVar.concat(getParameters(), newParameters));
 228         firstBlock.setExit(new Jump(f.firstBlock.createOccurrence(), ValRef.createOccurrences(newParameters)));
 229         context.markModified("SSAFunction.simplify-simple-lambda");
 230     }
 231
 232     public void setReturnCont(ReturnCont returnCont) {
 233         this.returnCont = returnCont;
 234         returnCont.setParent(this);
 235     }
 236
 237     /*public void tryToMakeMonadic(SSASimplificationContext context) {
 238         if(monadic)
 239             return;
 240         if(!Types.isApply(BTypes.PROC, 1, getReturnType()))
 241             return;
 242         for(ValRef ref = target.getOccurrence(); ref != null; ref = ref.getNext()) {
 243             ValRefBinder parent = ref.getParent();
 244             if(!(parent instanceof LetApply))
 245                 return;
 246             LetApply apply = (LetApply)parent;
 247             if(apply.getFunction() != ref)
 248                 return;
 249             if(apply.getParameters().length != getParameters().length)
 250                 return;
 251             if(!apply.hasEffect())
 252                 return;
 253         }
 254         makeMonadic(context);
 255     }*/
 256
 257     /*private void makeMonadic(SSASimplificationContext context) {
 258         Type oldReturnType = returnCont.getType();
 259         Type newReturnType;
 260         try {
 261             newReturnType = Types.matchApply(BTypes.PROC, oldReturnType);
 262         } catch (MatchException e) {
 263             throw new InternalCompilerError();
 264         }
 265
 266         //
 267         returnCont.setType(newReturnType);
 268         monadic = true;
 269
 270         //
 271         SSABlock block = new SSABlock(oldReturnType);
 272         addBlock(block);
 273
 274         returnCont.replaceWith(block);
 275
 276         BoundVar x = new BoundVar(newReturnType);
 277         LetApply apply = new LetApply(x, block.parameters[0].createOccurrence());
 278         apply.setMonadic(true);
 279         block.addStatement(apply);
 280
 281         block.setExit(new Jump(returnCont.createOccurrence(), x.createOccurrence()));
 282         context.markModified("SSAFunction.make-monadic");
 283     }*/
 284
 285     public ValRef isEqualToConstant() {
 286         if(firstBlock.parameters.length > 0)
 287             return null;
 288         if(firstBlock != lastBlock)
 289             return null;
 290         if(firstBlock.firstStatement != null)
 291             return null;
 292         if(!(firstBlock.exit instanceof Jump))
 293             return null;
 294         Jump exit = (Jump)firstBlock.exit;
 295         if(exit.getTarget().getBinding() != returnCont)
 296             return null;
 297         return exit.getParameters()[0];
 298     }
 299
 300     public BoundVar[] getParameters() {
 301         return firstBlock.parameters;
 302     }
 303
 304     public Type[] getParameterTypes() {
 305         return Types.getTypes(firstBlock.parameters);
 306     }
 307
 308     public int getArity() {
 309         return firstBlock.parameters.length;
 310     }
 311
 312     public void markGenerateOnFly() {
 313         for(SSABlock block = firstBlock; block != null; block = block.next)
 314             block.markGenerateOnFly();
 315     }
 316
 317     public SSAFunction copy(CopyContext context) {
 318         TVar[] newTypeParameters = context.copyParameters(typeParameters);
 319         SSAFunction newFunction = new SSAFunction(newTypeParameters, effect, context.copy(returnCont));
 320         for(SSABlock block = firstBlock;
 321                 block != null; block = block.next)
 322             newFunction.addBlock(context.copy(block));
 323         return newFunction;
 324     }
 325
 326     public SSAFunction copy() {
 327         return copy(new CopyContext());
 328     }
 329
 330     public void replace(TVar[] vars, Type[] replacements) {
 331         returnCont.replace(vars, replacements);
 332         for(SSABlock block = firstBlock;
 333                 block != null; block = block.next)
 334             block.replace(vars, replacements);
 335     }
 336
 337     public void setTypeParameters(TVar[] typeParameters) {
 338         this.typeParameters = typeParameters;
 339     }
 340
 341     public Type getType() {
 342         Type type = returnCont.getType();
 343         type = Types.functionE(
 344                 Types.getTypes(firstBlock.parameters),
 345                 effect,
 346                 type);
 347         type = Types.forAll(typeParameters, type);
 348         return type;
 349     }
 350
 351     public void mergeBlocks(SSAFunction function) {
 352         SSABlock block = function.firstBlock;
 353         while(block != null) {
 354             SSABlock next = block.next;
 355             addBlock(block);
 356             block = next;
 357         }
 358     }
 359
 360     public Type getReturnType() {
 361         return returnCont.getType();
 362     }
 363
 364     public void destroy() {
 365         for(SSABlock block = firstBlock;
 366                 block != null; block = block.next)
 367             block.destroy();
 368     }
 369
 370     public void detach() {
 371         if(prev == null)
 372             parent.setFirstFunction(next);
 373         else
 374             prev.next = next;
 375         if(next != null)
 376             next.prev = prev;
 377     }
 378
 379     public void remove() {
 380         destroy();
 381         detach();
 382     }
 383
 384     public void addSibling(SSAFunction function) {
 385         function.parent = parent;
 386         function.next = next;
 387         function.prev = this;
 388
 389         next.prev = function;
 390         next = function;
 391     }
 392
 393     public SSAFunction getNext() {
 394         return next;
 395     }
 396
 397     public void setParent(FunctionBinder parent) {
 398         this.parent = parent;
 399     }
 400
 401     public void setPrev(SSAFunction function) {
 402         this.prev = function;
 403     }
 404
 405     public void setNext(SSAFunction function) {
 406         this.next = function;
 407     }
 408
 409     public void collectFreeVariables(ArrayList<ValRef> vars) {
 410         for(SSABlock block = firstBlock;
 411                 block != null; block = block.next)
 412             block.collectFreeVariables(this, vars);
 413     }
 414
 415     @Override
 416     public SSAFunction getParentFunction() {
 417         return parent.getParentFunction();
 418     }
 419
 420     public FunctionBinder getParent() {
 421         return parent;
 422     }
 423
 424     public void lambdaLift(SSALambdaLiftingContext context) {
 425         for(SSABlock block = firstBlock;
 426                 block != null; block = block.next)
 427             block.lambdaLift(context);
 428     }
 429
 430     public void addParametersInFront(BoundVar[] parameters) {
 431         Cont proxy = null;
 432         for(ContRef ref = firstBlock.getOccurrence(); ref != null; ref = ref.getNext())
 433             proxy = ref.addParametersInFront(parameters, firstBlock.parameters, proxy);
 434
 435         firstBlock.parameters = BoundVar.concat(parameters, firstBlock.parameters);
 436         for(BoundVar parameter : parameters)
 437             parameter.parent = firstBlock;
 438     }
 439
 440     public void apply(ValRef[] parameters) {
 441         if(parameters.length == 0)
 442             return;
 443         if(firstBlock.hasNoOccurences()) {
 444             BoundVar[] vars = firstBlock.getParameters();
 445             for(int i=0;i<parameters.length;++i)
 446                 vars[i].replaceBy(parameters[i]);
 447             firstBlock.setParameters(Arrays.copyOfRange(vars, parameters.length, vars.length));
 448         }
 449         else {
 450             BoundVar[] newVars = new BoundVar[getArity()-parameters.length];
 451             SSABlock block = new SSABlock(newVars);
 452             block.setExit(new Jump(firstBlock.createOccurrence(),
 453                     ValRef.concat(ValRef.copy(parameters), ValRef.createOccurrences(newVars))));
 454             addBlockInFront(block);
 455         }
 456     }
 457
 458     public void applyTypes(Type[] types) {
 459         if(types.length == 0)
 460             return;
 461         if(types.length == typeParameters.length) {
 462             replace(typeParameters, types);
 463             typeParameters = TVar.EMPTY_ARRAY;
 464         }
 465         else {
 466             replace(Arrays.copyOf(typeParameters, types.length), types);
 467             typeParameters =
 468                     Arrays.copyOfRange(typeParameters,
 469                             types.length, typeParameters.length);
 470         }
 471     }
 472
 473     public boolean isSimpleEnoughForInline() {
 474         return firstBlock == lastBlock &&
 475                 (firstBlock.firstStatement == null ||
 476                 (firstBlock.firstStatement == firstBlock.lastStatement
 477                 && firstBlock.firstStatement instanceof LetApply));
 478     }
 479
 480     public Type getEffect() {
 481         return effect;
 482     }
 483
 484     public int getBlockCount() {
 485         int count = 0;
 486         for(SSABlock block = firstBlock;block != null;block = block.next)
 487             ++count;
 488         return count;
 489     }
 490
 491 }