bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/constants/SCLConstant.java

   1 package org.simantics.scl.compiler.constants;\r
   2 \r
   3 import java.util.ArrayList;\r
   4 import java.util.Arrays;\r
   5 \r
   6 import org.simantics.scl.compiler.common.names.Name;\r
   7 import org.simantics.scl.compiler.common.names.Named;\r
   8 import org.simantics.scl.compiler.internal.codegen.optimization.Optimization;\r
   9 import org.simantics.scl.compiler.internal.codegen.optimization.OptimizationMap;\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.SSAFunction;\r
  15 import org.simantics.scl.compiler.internal.codegen.ssa.exits.Jump;\r
  16 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;\r
  17 import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetFunctions;\r
  18 import org.simantics.scl.compiler.internal.codegen.utils.SSASimplificationContext;\r
  19 import org.simantics.scl.compiler.types.TVar;\r
  20 import org.simantics.scl.compiler.types.Type;\r
  21 import org.simantics.scl.compiler.types.Types;\r
  22 \r
  23 public class SCLConstant extends DelegateConstant implements Named {\r
  24 \r
  25     public Name name; // Needed only for debugging\r
  26     public SSAFunction definition;\r
  27     public SSAFunction inlinableDefinition;\r
  28     public int inlineArity = Integer.MAX_VALUE;\r
  29     public int inlinePhaseMask = 0xffffffff;\r
  30     public boolean isPrivate = false;    \r
  31     \r
  32     public SCLConstant(Name name, Type type) {\r
  33         super(type);\r
  34         this.name = name;\r
  35     }\r
  36     \r
  37     public void setInlineArity(int inlineArity, int inlinePhaseMask) {\r
  38         this.inlineArity = inlineArity;\r
  39         this.inlinePhaseMask = inlinePhaseMask;\r
  40         //System.out.println(name + " " + inlineArity + " " + inlinePhaseMask);\r
  41     }\r
  42     \r
  43     public void setPrivate(boolean isPrivate) {\r
  44         this.isPrivate = isPrivate;\r
  45     }\r
  46     \r
  47     public void setDefinition(SSAFunction definition) {\r
  48         this.definition = definition;\r
  49     }\r
  50     \r
  51     public SSAFunction getDefinition() {\r
  52         return definition;\r
  53     }\r
  54 \r
  55     @Override\r
  56     public void inline(SSASimplificationContext context, LetApply apply) {\r
  57         if(inlineTailCallToSelf(context, apply)) {\r
  58             return;\r
  59         }\r
  60         /*if(tryBetaReduce(context, apply)) {\r
  61             return;\r
  62         }*/\r
  63         if(basicInline(context, apply)) {\r
  64             return;\r
  65         }\r
  66         trySpecialize(context, apply);\r
  67         \r
  68         Optimization opt = OptimizationMap.OPTIMIZATIONS.get(name);\r
  69         if(opt != null)\r
  70             opt.inline(context, apply);\r
  71     }\r
  72 \r
  73     static int inlineCount = 0;\r
  74     \r
  75     private boolean canInlineInPhase(int phase) {\r
  76         return ((inlinePhaseMask >> phase)&1) == 1;\r
  77     }\r
  78     \r
  79     private boolean basicInline(SSASimplificationContext context, LetApply apply) {\r
  80         if(!canInlineInPhase(context.getPhase())) {\r
  81             //System.out.println("Cannot optimize " + name + " in phase " + context.getPhase());\r
  82             return false;\r
  83         }\r
  84         ValRef functionRef = apply.getFunction();\r
  85         ValRef[] parameters = apply.getParameters();\r
  86         SSAFunction def = inlinableDefinition == null ? definition : inlinableDefinition;\r
  87         if(parameters.length < inlineArity &&\r
  88                 (!isPrivate \r
  89                         || parameters.length != def.getArity() \r
  90                         || hasMoreThanOneOccurences()))\r
  91             return false;\r
  92         \r
  93         //if(def.getArity() == 0)\r
  94         //    return false; // FIXME\r
  95         \r
  96         //System.out.println("basicInline: " + apply);\r
  97         //System.out.println("def: " + def);\r
  98         \r
  99         if(isPrivate && !hasMoreThanOneOccurences())\r
 100             context.removeConstant(name);\r
 101         else\r
 102             def = (SSAFunction)def.copy();\r
 103         \r
 104         if(parameters.length >= def.getArity()) {\r
 105             if(parameters.length != def.getArity())\r
 106                 apply.split(def.getArity());\r
 107             apply.inline(def);\r
 108             context.markModified("SCLConstant.beta-constant " + getName());\r
 109         }\r
 110         else /*if(parameters.length < def.getArity())*/ {\r
 111             def.applyTypes(functionRef.getTypeParameters());\r
 112             def.apply(parameters);\r
 113                         \r
 114             def.setTarget(apply.getTarget());\r
 115             new LetFunctions(def).insertBefore(apply);\r
 116 \r
 117             apply.remove();\r
 118             context.markModified("SCLConstant.partial-beta-constant " + getName());\r
 119         }\r
 120                         \r
 121         /*Name newName = Name.create(name.module,\r
 122                 name.name + "_S" + (++inlineCount));\r
 123         SCLConstant newConstant = new SCLConstant(newName, type);\r
 124         newConstant.setPrivate(true);\r
 125         newConstant.setDefinition(definition.copy());    */    \r
 126         /*System.out.println("*** 1 *************************************");\r
 127         System.out.println(definition);\r
 128         System.out.println("*** 2 *************************************");\r
 129         System.out.println(newConstant.definition);\r
 130         \r
 131         function.remove();\r
 132         apply.setFunction(newConstant.createOccurrence(function.getTypeParameters()));\r
 133         \r
 134         context.addConstant(newConstant);\r
 135         \r
 136         context.markModified();\r
 137         \r
 138         newConstant.trySpecialize(context, apply);\r
 139         */\r
 140         \r
 141         return true;\r
 142     }\r
 143 \r
 144     private boolean inlineTailCallToSelf(SSASimplificationContext context, LetApply apply) {\r
 145         SSAFunction thisFunction = apply.getParent().getParent();\r
 146         if(thisFunction != definition)\r
 147             return false;\r
 148         ValRef ref = apply.getTarget().getOccurrence();\r
 149         if(ref == null || ref.getNext() != null)\r
 150             return false;\r
 151         if(!(ref.getParent() instanceof Jump))\r
 152             return false;\r
 153         Jump jump = (Jump)ref.getParent();\r
 154         if(jump.getParameters().length != 1)\r
 155             return false;\r
 156         if(jump.getTarget().getBinding() != thisFunction.getReturnCont())\r
 157             return false;\r
 158         if(apply.getParameters().length != thisFunction.getArity())\r
 159             return false;\r
 160         \r
 161         jump.getTarget().remove();\r
 162         jump.setTarget(thisFunction.getFirstBlock().createOccurrence());\r
 163         jump.setParameters(apply.getParameters());\r
 164         \r
 165         apply.getFunction().remove();\r
 166         apply.detach();\r
 167         \r
 168         context.markModified("SCLConstant.simplify-tail-call");\r
 169         \r
 170         return true;\r
 171     }\r
 172 \r
 173     private void trySpecialize(SSASimplificationContext context, LetApply apply) {\r
 174         if(!isPrivate)\r
 175             return;\r
 176         if(hasMoreThanOneOccurences())\r
 177             return;\r
 178         if(apply.getParent().getParent() == definition)\r
 179             return;\r
 180 \r
 181         // Specialization of type parameters\r
 182         {\r
 183             ValRef functionRef = apply.getFunction();\r
 184             Type[] pValues = functionRef.getTypeParameters();   \r
 185             boolean hasComplexTypes = false;\r
 186             for(Type type : pValues)\r
 187                 if(!(Types.canonical(type) instanceof TVar)) {\r
 188                     hasComplexTypes = true;\r
 189                     break;\r
 190                 }\r
 191             if(hasComplexTypes) {                \r
 192                 /*PrintingContext pc = new PrintingContext();\r
 193                 pc.append(">> BEFORE >>\n");\r
 194                 definition.toString(pc);*/   \r
 195                 \r
 196                 TVar[] pVars = definition.getTypeParameters();\r
 197                 TVar[] pVarsTail;\r
 198                 if(pVars.length == pValues.length)\r
 199                     pVarsTail = TVar.EMPTY_ARRAY;\r
 200                 else {\r
 201                     pVarsTail = Arrays.copyOfRange(pVars, pValues.length, pVars.length);\r
 202                     pVars = Arrays.copyOf(pVars, pValues.length);\r
 203                 }\r
 204                 type = Types.instantiate(type, pValues);\r
 205                 /*pc.append("REPLACE: ");\r
 206                 pc.append(pVars);\r
 207                 pc.append(" -> ");\r
 208                 pc.append(pValues);\r
 209                 pc.append('\n');*/\r
 210                 definition.replace(pVars, pValues);\r
 211                 TVar[] newParameters = Types.freeVarsArray(pValues);\r
 212                 type = Types.forAll(newParameters, type);\r
 213                 functionRef.setTypeParameters(newParameters);\r
 214                 definition.setTypeParameters(Types.concat(newParameters, pVarsTail));               \r
 215                 \r
 216                 /*pc.append(">> AFTER >>\n");\r
 217                 definition.toString(pc);\r
 218                 System.out.println(pc);*/\r
 219                 context.markModified("SCLConstant.specialize-types");\r
 220             }\r
 221         }\r
 222         \r
 223         if(!definition.getFirstBlock().hasNoOccurences())\r
 224             // TODO We can flex this requirement if all jumps to the first block\r
 225             //      give same values to the first block\r
 226             return;\r
 227         \r
 228         // Specialization of parameters\r
 229         ValRef[] parameters = apply.getParameters();\r
 230         ValRef[] specialization = null;\r
 231         int arity = Math.min(parameters.length, definition.getArity());\r
 232         for(int i=0;i<arity;++i) {\r
 233             Val val = parameters[i].getBinding();\r
 234             if(val instanceof Constant) {\r
 235                 if(specialization == null)\r
 236                     specialization = new ValRef[arity];\r
 237                 specialization[i] = parameters[i];\r
 238             }\r
 239         }\r
 240         \r
 241         if(specialization != null)\r
 242             specialize(context, apply, specialization);\r
 243     }\r
 244 \r
 245     private void specialize(SSASimplificationContext context, LetApply apply,\r
 246             ValRef[] specialization) {\r
 247         /*System.out.println("=== SPECIALIZE ====================");\r
 248         System.out.println(apply);\r
 249         System.out.println("--------");\r
 250         System.out.println(definition);\r
 251         System.out.println("========");*/\r
 252         // *** Modify apply *******************************        \r
 253         {\r
 254             // Handle old parameters\r
 255             ValRef[] oldParameters = apply.getParameters();\r
 256             int newParameterCount = oldParameters.length - specialization.length;\r
 257             for(int i=0;i<specialization.length;++i)\r
 258                 if(specialization[i] == null)\r
 259                     ++newParameterCount;            \r
 260 \r
 261             if(newParameterCount == 0) {\r
 262                 // If apply would be degenerated, remove it\r
 263                 apply.getTarget().replaceBy(apply.getFunction());\r
 264                 apply.remove();\r
 265             }            \r
 266             else {\r
 267                 // Create new parameter array\r
 268                 ValRef[] newParameters = new ValRef[newParameterCount];\r
 269                 int k=0;\r
 270                 for(int i=0;i<specialization.length;++i)\r
 271                     if(specialization[i] == null)\r
 272                         newParameters[k++] = oldParameters[i];\r
 273                     else\r
 274                         oldParameters[i].remove();                        \r
 275                 for(int i=specialization.length;i<oldParameters.length;++i)\r
 276                     newParameters[k++] = oldParameters[i];\r
 277                         \r
 278                 apply.setParameters(newParameters);\r
 279             }\r
 280         }\r
 281         \r
 282         // *** Modify definition **************************        \r
 283         {\r
 284             SSABlock firstBlock = definition.getFirstBlock();\r
 285             BoundVar[] parameters = firstBlock.getParameters();\r
 286             ArrayList<BoundVar> newParameters = new ArrayList<BoundVar>(parameters.length); \r
 287             for(int i=0;i<specialization.length;++i)\r
 288                 if(specialization[i] != null)\r
 289                     parameters[i].replaceBy(specialization[i]);\r
 290                 else\r
 291                     newParameters.add(parameters[i]);\r
 292             for(int i=specialization.length;i<parameters.length;++i)\r
 293                 newParameters.add(parameters[i]);\r
 294             firstBlock.setParameters(newParameters.toArray(new BoundVar[newParameters.size()]));\r
 295             \r
 296             type = definition.getType();\r
 297         }\r
 298         \r
 299         /*System.out.println(apply);\r
 300         System.out.println("--------");\r
 301         System.out.println(definition);*/\r
 302         context.markModified("SCLConstant.specialize");  \r
 303     }\r
 304 \r
 305     @Override\r
 306     public String toString() {\r
 307         char c = name.name.charAt(0);\r
 308         if(Character.isJavaIdentifierStart(c) || name.name.charAt(0) == '(' || c == '[')\r
 309             return name.name;\r
 310         else\r
 311             return "(" + name.name + ")";\r
 312     }\r
 313 \r
 314     @Override\r
 315     public Name getName() {\r
 316         return name;\r
 317     }\r
 318 \r
 319     public Constant getBase() {\r
 320         return base;\r
 321     }\r
 322     \r
 323     public boolean isPrivate() {\r
 324         return isPrivate;\r
 325     }\r
 326 \r
 327     private boolean simplifyConstantFunction(SSASimplificationContext context) {\r
 328         ValRef constant = definition.isEqualToConstant();\r
 329         if(constant == null)\r
 330             return false;\r
 331         Val binding = constant.getBinding();\r
 332         if(binding == this)\r
 333             return false;\r
 334         if(binding instanceof Constant) {\r
 335             /*System.out.println(name + " -> " + constant.getBinding());\r
 336             System.out.println("replace: " + this);\r
 337             System.out.println("of type: " + this.getType());\r
 338             System.out.println("by: " + binding);\r
 339             System.out.println("of type: " + binding.getType());\r
 340             System.out.println("parameters: " + Types.toString(definition.getTypeParameters()));\r
 341             System.out.println("parameters2: " + Types.toString(constant.getTypeParameters()));\r
 342             System.out.println("private: " + isPrivate);*/            \r
 343             replaceBy(binding,\r
 344                     definition.getTypeParameters(), \r
 345                     constant.getTypeParameters());                \r
 346             if(isPrivate) {\r
 347                 definition.destroy();\r
 348                 context.removeConstant(name);\r
 349             }\r
 350             context.markModified("SCLConstant.simplify-constant");\r
 351             return true;\r
 352         }\r
 353         return false;\r
 354     }\r
 355     \r
 356     public void simplify(SSASimplificationContext context) {\r
 357         if(!hasNoOccurences() /* TODO why this condition is needed? */) {\r
 358             if(simplifyConstantFunction(context))\r
 359                 return;\r
 360         }\r
 361         /*if(isPrivate)\r
 362             definition.tryToMakeMonadic(context);*/\r
 363         definition.simplify(context);\r
 364         if(inlineArity == Integer.MAX_VALUE && definition.isSimpleEnoughForInline()) {\r
 365             inlineArity = definition.getArity();\r
 366             inlinableDefinition = (SSAFunction)definition.copy();\r
 367             context.markModified("mark inlineable " + name);\r
 368             // FIXME this will make self calling function inlinable that may crash the compiler\r
 369         }\r
 370     }\r
 371 \r
 372     public void saveInlinableDefinition() {\r
 373         if(inlineArity < Integer.MAX_VALUE)\r
 374             inlinableDefinition = (SSAFunction)definition.copy();\r
 375     }\r
 376 }\r