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