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