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