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

   1 package org.simantics.scl.compiler.internal.codegen.ssa.statements;\r
   2 \r
   3 import java.util.ArrayList;\r
   4 import java.util.Arrays;\r
   5 \r
   6 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;\r
   7 import org.simantics.scl.compiler.constants.Constant;\r
   8 import org.simantics.scl.compiler.internal.codegen.continuations.ContRef;\r
   9 import org.simantics.scl.compiler.internal.codegen.references.BoundVar;\r
  10 import org.simantics.scl.compiler.internal.codegen.references.Val;\r
  11 import org.simantics.scl.compiler.internal.codegen.references.ValRef;\r
  12 import org.simantics.scl.compiler.internal.codegen.ssa.SSABlock;\r
  13 import org.simantics.scl.compiler.internal.codegen.ssa.SSAExit;\r
  14 import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;\r
  15 import org.simantics.scl.compiler.internal.codegen.ssa.SSAStatement;\r
  16 import org.simantics.scl.compiler.internal.codegen.ssa.binders.BoundVarBinder;\r
  17 import org.simantics.scl.compiler.internal.codegen.ssa.binders.ValRefBinder;\r
  18 import org.simantics.scl.compiler.internal.codegen.ssa.exits.Jump;\r
  19 import org.simantics.scl.compiler.internal.codegen.ssa.exits.Switch;\r
  20 import org.simantics.scl.compiler.internal.codegen.utils.CopyContext;\r
  21 import org.simantics.scl.compiler.internal.codegen.utils.MethodBuilder;\r
  22 import org.simantics.scl.compiler.internal.codegen.utils.PrintingContext;\r
  23 import org.simantics.scl.compiler.internal.codegen.utils.SSASimplificationContext;\r
  24 import org.simantics.scl.compiler.internal.codegen.utils.SSAValidationContext;\r
  25 import org.simantics.scl.compiler.top.SCLCompilerConfiguration;\r
  26 import org.simantics.scl.compiler.types.TVar;\r
  27 import org.simantics.scl.compiler.types.Type;\r
  28 import org.simantics.scl.compiler.types.Types;\r
  29 import org.simantics.scl.compiler.types.exceptions.MatchException;\r
  30 import org.simantics.scl.compiler.types.util.MultiFunction;\r
  31 import org.simantics.scl.compiler.types.util.TypeUnparsingContext;\r
  32 \r
  33 public class LetApply extends LetStatement implements ValRefBinder {\r
  34     private ValRef function;\r
  35     private ValRef[] parameters;\r
  36     Type effect;\r
  37     \r
  38     public LetApply(BoundVar target, Type effect, ValRef function, ValRef ... parameters) {\r
  39         super(target);\r
  40         if(SCLCompilerConfiguration.DEBUG) {\r
  41             if(effect == null)\r
  42                 throw new InternalCompilerError();\r
  43             if(function.getBinding() == null)\r
  44                 throw new InternalCompilerError();\r
  45         }\r
  46         this.setFunction(function);\r
  47         this.setParameters(parameters);\r
  48         this.effect = Types.canonical(effect);\r
  49     }\r
  50 \r
  51     public void push(MethodBuilder mb) {\r
  52         //mb.getCodeBuilder().mapLineNumber(lineNumber);\r
  53         Val f = getFunction().getBinding();\r
  54         Val[] ps = ValRef.getBindings(getParameters());\r
  55         if(f instanceof Constant) {\r
  56             Constant cf = (Constant)f;\r
  57             Type returnType = cf.apply(mb, getFunction().getTypeParameters(), ps);\r
  58             if(Types.isBoxed(returnType))\r
  59                 mb.unbox(target.getType());\r
  60         }\r
  61         else {            \r
  62             mb.push(f, f.getType());\r
  63             mb.pushBoxed(ps);\r
  64             mb.genericApply(ps.length);\r
  65             mb.unbox(target.getType());\r
  66         }\r
  67     }\r
  68     \r
  69     @Override\r
  70     public void generateCode(MethodBuilder mb) {\r
  71         if(!target.generateOnFly) {\r
  72             push(mb);\r
  73             mb.store(target);\r
  74         }\r
  75     }\r
  76 \r
  77     @Override\r
  78     public void toString(PrintingContext context) {\r
  79         if(determineGenerateOnFly())\r
  80             context.addInlineExpression(target, this);\r
  81         else\r
  82             toStringAux(context);\r
  83     }\r
  84     \r
  85     private void toStringAux(PrintingContext context) {\r
  86         context.indentation();\r
  87         context.append(target);\r
  88         context.append("(" + target.occurrenceCount() + ")");\r
  89         context.append(" = ");\r
  90         bodyToString(context);\r
  91         context.append('\n');\r
  92         \r
  93     }\r
  94     \r
  95     public void bodyToString(PrintingContext context) {\r
  96         if(context.getErrorMarker() == this)\r
  97             context.append("!> ");\r
  98         if(hasEffect()) {\r
  99             context.append("<");\r
 100             context.append(effect);\r
 101             context.append("> ");\r
 102         }\r
 103         context.append(getFunction());\r
 104         for(ValRef parameter : getParameters()) {\r
 105             context.append(' ');\r
 106             context.append(parameter);\r
 107         }\r
 108     }\r
 109     \r
 110     @Override\r
 111     public String toString() {\r
 112         PrintingContext context = new PrintingContext();\r
 113         toStringAux(context);\r
 114         return context.toString();\r
 115     }\r
 116 \r
 117     @Override\r
 118     public void validate(SSAValidationContext context) {\r
 119         context.validate(target);\r
 120         if(target.getParent() != this)\r
 121             throw new InternalCompilerError();\r
 122         context.validate(function);\r
 123         if(function.getParent() != this)\r
 124             throw new InternalCompilerError();\r
 125         for(ValRef parameter : parameters) {\r
 126             context.validate(parameter);\r
 127             if(parameter.getParent() != this)\r
 128                 throw new InternalCompilerError();\r
 129         }\r
 130         //if(parameters.length == 0)\r
 131         //    throw new InternalCompilerError();\r
 132         \r
 133         \r
 134         MultiFunction mFun;\r
 135         try {\r
 136             mFun = Types.matchFunction(getFunction().getType(), getParameters().length);\r
 137         } catch (MatchException e) {\r
 138             context.setErrorMarker(this);\r
 139             throw new InternalCompilerError();\r
 140         }\r
 141         for(int i=0;i<getParameters().length;++i)\r
 142             context.assertSubsumes(this, getParameters()[i].getType(), mFun.parameterTypes[i]);\r
 143         context.assertSubsumes(this, target.getType(), mFun.returnType);\r
 144         context.assertEqualsEffect(this, effect, mFun.effect);\r
 145     }\r
 146 \r
 147     @Override\r
 148     public void destroy() {\r
 149         getFunction().remove();\r
 150         for(ValRef parameter : getParameters())\r
 151             parameter.remove();\r
 152     }\r
 153     \r
 154     @Override\r
 155     public void simplify(SSASimplificationContext context) {\r
 156         if(target.hasNoOccurences() && !hasEffect()) {\r
 157             remove();\r
 158             context.markModified("LetApply.dead-let-statement");\r
 159             return;\r
 160         }\r
 161         Val functionVal = getFunction().getBinding();\r
 162         if(functionVal instanceof BoundVar) {\r
 163             BoundVarBinder parent_ = ((BoundVar)functionVal).parent;\r
 164             if(parent_ instanceof SSAFunction) {\r
 165                 SSAFunction function = (SSAFunction)parent_;\r
 166                 if(functionVal.hasMoreThanOneOccurences())\r
 167                     return;\r
 168                 if(getParameters().length < function.getArity())\r
 169                     return;\r
 170                 if(getParameters().length > function.getArity())\r
 171                     split(function.getArity());\r
 172                 inline(function);\r
 173                 function.detach();\r
 174                 context.markModified("LetApply.beta-lambda");\r
 175             }\r
 176             else if(parent_ instanceof LetApply) {\r
 177                 LetApply apply = (LetApply)parent_;\r
 178                 if(apply.hasEffect())\r
 179                     return;\r
 180                 boolean hasJustOneOccurence = !functionVal.hasMoreThanOneOccurences();\r
 181                 if((hasJustOneOccurence && apply.getParent() == getParent()) ||\r
 182                         apply.isPartial()) {\r
 183                     if(hasJustOneOccurence) {\r
 184                         apply.detach();\r
 185                         setFunction(apply.getFunction());\r
 186                         setParameters(ValRef.concat(apply.getParameters(), getParameters()));\r
 187                     }\r
 188                     else {\r
 189                         setFunction(apply.getFunction().copy());\r
 190                         setParameters(ValRef.concat(ValRef.copy(apply.getParameters()), getParameters()));\r
 191                     }\r
 192                     context.markModified("LetApply.merge-applications");\r
 193                 }\r
 194             }\r
 195             else if(parent_ instanceof SSABlock) {\r
 196                 SSABlock parent = getParent();\r
 197                 if(parent_ != parent)\r
 198                     return;\r
 199                 if(parent.getFirstStatement() != this)\r
 200                     return;\r
 201                 if(!parent.hasMoreThanOneOccurences())\r
 202                     return; // We stop here, because situation can be handled by better transformations\r
 203                 if(functionVal.hasMoreThanOneOccurences())\r
 204                     return;\r
 205                 // We have now the following situation:\r
 206                 //    [c] ... f ... =\r
 207                 //        x = f ... \r
 208                 // * this application is the only reference to f\r
 209                 // * there are multiple references to [c]\r
 210                 for(ContRef ref = parent.getOccurrence();ref != null; ref = ref.getNext())\r
 211                     if(!(ref.getParent() instanceof Jump))\r
 212                         return;\r
 213                 \r
 214                 // Finds the position of the functionVal in the parameter list of \r
 215                 // the parent block.\r
 216                 int position;\r
 217                 for(position=0;position<parent.getParameters().length;++position)\r
 218                     if(parent.getParameters()[position] == functionVal)\r
 219                         break;\r
 220                 if(position == parent.getParameters().length)\r
 221                     throw new InternalCompilerError();\r
 222                 \r
 223                 // Do tranformation\r
 224                 for(ContRef ref = parent.getOccurrence();ref != null; ref = ref.getNext()) {\r
 225                     Jump jump = (Jump)ref.getParent();\r
 226                     SSABlock block = jump.getParent();\r
 227                     \r
 228                     BoundVar newTarget = new BoundVar(target.getType());\r
 229                     block.addStatement(new LetApply(newTarget, effect, jump.getParameter(position), ValRef.copy(parameters)));\r
 230                     jump.setParameter(position, newTarget.createOccurrence());\r
 231                 }\r
 232                 \r
 233                 parent.setParameter(position, target);\r
 234                 remove();\r
 235                 context.markModified("LetApply.hoist-apply");\r
 236             }\r
 237         }\r
 238         else if(functionVal instanceof Constant) {\r
 239             ((Constant)functionVal).inline(context, this);\r
 240         }\r
 241     }\r
 242     \r
 243     public boolean isPartial() {\r
 244         return parameters.length < function.getBinding().getEffectiveArity();\r
 245     }\r
 246 \r
 247     /**\r
 248      * Removes apply if it does not have parameters.\r
 249      */\r
 250     public void removeDegenerated() {\r
 251         if(getParameters().length == 0) {\r
 252             target.replaceBy(getFunction());\r
 253             getFunction().remove();\r
 254             detach();\r
 255         }\r
 256     }\r
 257 \r
 258     public boolean determineGenerateOnFly() {\r
 259         if(hasEffect())\r
 260             return false;\r
 261         ValRef ref = target.getOccurrence();\r
 262         if(ref == null || ref.getNext() != null)\r
 263             return false;\r
 264         Object parent = ref.getParent();\r
 265         if(parent instanceof SSAStatement) {\r
 266             if(((SSAStatement)parent).getParent() != getParent())\r
 267                 return false;\r
 268         }\r
 269         else if(parent instanceof SSAExit) {\r
 270             if(((SSAExit)parent).getParent() != getParent())\r
 271                 return false;\r
 272             if(parent instanceof Switch)\r
 273                 return false;\r
 274         }\r
 275         else\r
 276             return false;\r
 277         return true;\r
 278     }\r
 279     \r
 280     @Override\r
 281     public void markGenerateOnFly() {        \r
 282         target.generateOnFly = determineGenerateOnFly();\r
 283     }\r
 284 \r
 285     public ValRef getFunction() {\r
 286         return function;\r
 287     }\r
 288 \r
 289     public void setFunction(ValRef function) {\r
 290         this.function = function;\r
 291         function.setParent(this);\r
 292     }\r
 293 \r
 294     public ValRef[] getParameters() {\r
 295         return parameters;\r
 296     }\r
 297 \r
 298     public void setParameters(ValRef[] parameters) {\r
 299         /*if(SCLCompilerConfiguration.DEBUG)\r
 300             if(parameters.length == 0)\r
 301                 throw new InternalCompilerError();*/\r
 302         this.parameters = parameters;\r
 303         for(ValRef parameter : parameters)\r
 304             parameter.setParent(this);\r
 305     }\r
 306     \r
 307     @Override\r
 308     public SSAStatement copy(CopyContext context) {\r
 309         LetApply result = new LetApply(context.copy(target), \r
 310                 context.copyType(effect),\r
 311                 context.copy(function), \r
 312                 context.copy(parameters));\r
 313         return result;\r
 314     }\r
 315     \r
 316     @Override\r
 317     public void replace(TVar[] vars, Type[] replacements) {\r
 318         target.replace(vars, replacements);\r
 319         function.replace(vars, replacements);\r
 320         effect = effect.replace(vars, replacements);\r
 321         for(ValRef parameter : parameters)\r
 322             parameter.replace(vars, replacements);\r
 323     }\r
 324     \r
 325     /**\r
 326      * Inlines the application by the given function.\r
 327      * It is assumed that the function has the same number\r
 328      * of parameters as this one and there are no other \r
 329      * references to the function (copy function before\r
 330      * inlining if necessary).\r
 331      */\r
 332     public void inline(SSAFunction function) {\r
 333         if(function.getArity() != parameters.length)\r
 334             throw new InternalCompilerError();        \r
 335                \r
 336         SSABlock headBlock = getParent();\r
 337         SSAFunction thisFunction = headBlock.getParent();\r
 338                \r
 339         /*System.out.println("--- INLINING -------------------------------");\r
 340         System.out.println(thisFunction);\r
 341         System.out.println("Function name: " + getFunction().getBinding());\r
 342         System.out.println("++++++++++++++++++++++++++++++++++++++++++++");\r
 343         System.out.println(function);   \r
 344         */\r
 345         \r
 346         if(this.function.getTypeParameters().length > 0) {\r
 347             /*if(function.getParent() != null) {\r
 348                 PrintingContext pc = new PrintingContext();\r
 349                 pc.append("----------------------------\n");\r
 350                 function.getParent().getParentFunction().toString(pc);\r
 351                 pc.append("\n----\n");\r
 352                 function.toString(pc);\r
 353                 pc.append("\n");\r
 354                 pc.append(function.getTypeParameters());\r
 355                 pc.append(" -> ");\r
 356                 pc.append(this.function.getTypeParameters());\r
 357                 System.out.println(pc.toString());\r
 358             }*/\r
 359             function.replace(function.getTypeParameters(), this.function.getTypeParameters());\r
 360         }\r
 361 \r
 362         if(getPrev() != null)\r
 363             getPrev().setAsLastStatement();\r
 364         else\r
 365             headBlock.removeStatements();\r
 366         \r
 367         // Create tail block\r
 368         SSABlock tailBlock = new SSABlock(new BoundVar[] {target});\r
 369         thisFunction.addBlock(tailBlock);\r
 370         {\r
 371             SSAStatement stat = getNext();\r
 372             while(stat != null) {\r
 373                 SSAStatement temp = stat.getNext();\r
 374                 tailBlock.addStatement(stat);\r
 375                 stat = temp;\r
 376             }\r
 377         }\r
 378         tailBlock.setExit(headBlock.getExit());\r
 379         \r
 380         // Merge blocks        \r
 381         thisFunction.mergeBlocks(function);           \r
 382         \r
 383         headBlock.setExit(new Jump(function.getFirstBlock().createOccurrence(), \r
 384                 parameters));\r
 385         function.getReturnCont().replaceWith(tailBlock);\r
 386 \r
 387         this.function.remove();\r
 388         // Note: No need to remove or detach this statement anymore\r
 389         \r
 390         // TODO remove function\r
 391         /*\r
 392         System.out.println("============================================");\r
 393         System.out.println(thisFunction);\r
 394         */\r
 395     }\r
 396 \r
 397     @Override\r
 398     public void collectFreeVariables(SSAFunction parentFunction,\r
 399             ArrayList<ValRef> vars) {\r
 400         function.collectFreeVariables(parentFunction, vars);\r
 401         for(ValRef parameter : parameters)\r
 402             parameter.collectFreeVariables(parentFunction, vars);\r
 403     }\r
 404     \r
 405     @Override\r
 406     public void replaceByApply(ValRef valRef, Val newFunction, Type[] typeParameters, Val[] parameters) {\r
 407         if(function == valRef) {\r
 408             valRef.remove();\r
 409             setFunction(newFunction.createOccurrence(typeParameters));\r
 410             setParameters(ValRef.concat(ValRef.createOccurrences(parameters), this.parameters));\r
 411         }\r
 412         else\r
 413             super.replaceByApply(valRef, newFunction, typeParameters, parameters);\r
 414     }\r
 415 \r
 416     /**\r
 417      * Splits this application into two applications where the first has\r
 418      * the arity given as a parameter and the new application inserted \r
 419      * after this statement has the rest of the parameters.\r
 420      */\r
 421     public void split(int arity) {\r
 422         if(arity == parameters.length)\r
 423             return;\r
 424         if(arity > parameters.length)\r
 425             throw new InternalCompilerError();\r
 426         ValRef[] firstHalf = arity == 0 ? ValRef.EMPTY_ARRAY : Arrays.copyOf(parameters, arity);\r
 427         ValRef[] secondHalf = arity == parameters.length ? ValRef.EMPTY_ARRAY : Arrays.copyOfRange(parameters, arity, parameters.length);\r
 428         BoundVar newVar;\r
 429         try {\r
 430             MultiFunction mfun = Types.matchFunction(function.getType(), arity);\r
 431             newVar = new BoundVar(mfun.returnType);\r
 432         } catch (MatchException e) {\r
 433             throw new InternalCompilerError();\r
 434         }\r
 435         LetApply newApply = new LetApply(target, effect, \r
 436                 newVar.createOccurrence(), secondHalf);\r
 437         newApply.insertAfter(this);\r
 438         effect = Types.NO_EFFECTS;\r
 439         setTarget(newVar);\r
 440         setParameters(firstHalf);\r
 441     }\r
 442     \r
 443     /**\r
 444      * True, if the application may have side effects.\r
 445      */\r
 446     public boolean hasEffect() {\r
 447         return effect != Types.NO_EFFECTS;\r
 448     }\r
 449 \r
 450     public void updateEffect() {\r
 451         try {\r
 452             MultiFunction mFun = Types.matchFunction(function.getType(), parameters.length);\r
 453             this.effect = mFun.effect;\r
 454         } catch (MatchException e) {\r
 455             throw new InternalCompilerError(e);\r
 456         }\r
 457     }\r
 458     \r
 459     @Override\r
 460     public void prepare(MethodBuilder mb) {\r
 461         function.getBinding().prepare(mb);\r
 462     }\r
 463 }\r