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

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