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