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