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

   1 package org.simantics.scl.compiler.internal.codegen.ssa.statements;
   2
   3 import java.util.ArrayList;
   4
   5 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
   6 import org.simantics.scl.compiler.constants.Constant;
   7 import org.simantics.scl.compiler.constants.SCLConstant;
   8 import org.simantics.scl.compiler.internal.codegen.references.BoundVar;
   9 import org.simantics.scl.compiler.internal.codegen.references.ValRef;
  10 import org.simantics.scl.compiler.internal.codegen.ssa.SSAClosure;
  11 import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;
  12 import org.simantics.scl.compiler.internal.codegen.ssa.SSAStatement;
  13 import org.simantics.scl.compiler.internal.codegen.ssa.binders.ClosureBinder;
  14 import org.simantics.scl.compiler.internal.codegen.utils.CopyContext;
  15 import org.simantics.scl.compiler.internal.codegen.utils.MethodBuilder;
  16 import org.simantics.scl.compiler.internal.codegen.utils.PrintingContext;
  17 import org.simantics.scl.compiler.internal.codegen.utils.SSALambdaLiftingContext;
  18 import org.simantics.scl.compiler.internal.codegen.utils.SSASimplificationContext;
  19 import org.simantics.scl.compiler.internal.codegen.utils.SSAValidationContext;
  20 import org.simantics.scl.compiler.internal.codegen.utils.ValRefVisitor;
  21 import org.simantics.scl.compiler.types.TVar;
  22 import org.simantics.scl.compiler.types.Type;
  23 import org.simantics.scl.compiler.types.Types;
  24
  25 import gnu.trove.map.hash.THashMap;
  26 import gnu.trove.set.hash.THashSet;
  27
  28 public class LetFunctions extends SSAStatement implements ClosureBinder {
  29     long recursiveGroupLocation;
  30     SSAClosure firstClosure;
  31
  32     public LetFunctions() {
  33     }
  34
  35     public LetFunctions(SSAClosure closure) {
  36         firstClosure = closure;
  37         closure.setParent(this);
  38     }
  39
  40     @Override
  41     public void toString(PrintingContext context) {
  42         for(SSAClosure closure = firstClosure; closure != null; closure = closure.getNext()) {
  43             context.indentation();
  44             context.append(closure.getTarget());
  45             context.append("(" + closure.getTarget().occurrenceCount() + ")");
  46             context.append(" :: ");
  47             context.append(closure.getTarget().getType());
  48             context.append(" = \n");
  49             context.indent();
  50             closure.toString(context);
  51             context.dedent();
  52         }
  53     }
  54
  55     public void addClosure(SSAClosure closure) {
  56         closure.setParent(this);
  57         closure.setNext(firstClosure);
  58         if(firstClosure != null)
  59             firstClosure.setPrev(closure);
  60         firstClosure = closure;
  61     }
  62
  63     @Override
  64     public void generateCode(MethodBuilder mb) {
  65         throw new InternalCompilerError("Functions should be lambda lifted before code generation");
  66     }
  67
  68     @Override
  69     public void validate(SSAValidationContext context) {
  70         for(SSAClosure closure = firstClosure; closure != null; closure = closure.getNext()) {
  71             if(!(closure.getTarget() instanceof BoundVar))
  72                 throw new InternalCompilerError();
  73             closure.validate(context);
  74         }
  75     }
  76
  77     @Override
  78     public void destroy() {
  79         for(SSAClosure closure = firstClosure; closure != null; closure = closure.getNext())
  80             closure.destroy();
  81     }
  82
  83     @Override
  84     public SSAStatement copy(CopyContext context) {
  85         LetFunctions result = new LetFunctions();
  86         for(SSAClosure closure = firstClosure; closure != null; closure = closure.getNext()) {
  87             SSAClosure newFunction = closure.copy(context);
  88             newFunction.setTarget(context.copy(closure.getTarget()));
  89             result.addClosure(newFunction);
  90         }
  91         return result;
  92     }
  93
  94     @Override
  95     public void replace(TVar[] vars, Type[] replacements) {
  96         for(SSAClosure closure = firstClosure; closure != null; closure = closure.getNext()) {
  97             ((BoundVar)closure.getTarget()).replace(vars, replacements);
  98             closure.replace(vars, replacements);
  99         }
 100     }
 101
 102     @Override
 103     public void addBoundVariablesTo(SSAValidationContext context) {
 104         for(SSAClosure closure = firstClosure; closure != null; closure = closure.getNext())
 105             context.validBoundVariables.add((BoundVar)closure.getTarget());
 106     }
 107
 108     @Override
 109     public SSAClosure getFirstClosure() {
 110         return firstClosure;
 111     }
 112
 113     @Override
 114     public void setFirstClosure(SSAClosure function) {
 115         this.firstClosure = function;
 116         if(function == null)
 117             detach();
 118     }
 119
 120     @Override
 121     public void collectFreeVariables(SSAFunction parentFunction,
 122             ArrayList<ValRef> vars) {
 123         throw new InternalCompilerError("Should not be called for non-lambda-lifted functions.");
 124         // FIXME inefficient, some kind of caching needed here
 125         /*THashSet<BoundVar> tempVars = new THashSet<BoundVar>();
 126         for(SSAFunction function = firstFunction; function != null; function = function.getNext())
 127             function.collectFreeVariables(tempVars);
 128
 129         for(BoundVar var : tempVars)
 130             if(var.getFunctionParent() != parentFunction)
 131                 vars.add(var);*/
 132     }
 133
 134     @Override
 135     public void lambdaLift(SSALambdaLiftingContext context) {
 136         boolean hasValues = false;
 137         boolean isRecursive = false;
 138
 139         // Lambda lift substructure and collect free variables
 140         THashSet<BoundVar> targets = new THashSet<BoundVar>();
 141         ArrayList<ValRef> freeVars = new ArrayList<ValRef>();
 142         for(SSAClosure closure = firstClosure;
 143                 closure != null;
 144                 closure = closure.getNext()) {
 145             hasValues |= closure.isValue();
 146             closure.lambdaLift(context);
 147             targets.add((BoundVar)closure.getTarget());
 148             closure.collectFreeVariables(freeVars);
 149         }
 150
 151         if(!(firstClosure instanceof SSAFunction) && firstClosure.getNext() == null) {
 152             THashMap<BoundVar, BoundVar> varMap = new THashMap<BoundVar, BoundVar>();
 153             ArrayList<BoundVar> oldVarsList = new ArrayList<BoundVar>(4);
 154             ArrayList<BoundVar> newVarsList = new ArrayList<BoundVar>(4);
 155             BoundVar newTarget = null;
 156             for(ValRef ref : freeVars) {
 157                 BoundVar var = (BoundVar)ref.getBinding();
 158                 if(targets.contains(var)) {
 159                     if(newTarget == null)
 160                         newTarget = new BoundVar(var.getType());
 161                     ref.replaceBy(newTarget);
 162                     continue;
 163                 }
 164                 BoundVar newVar = varMap.get(var);
 165                 if(newVar == null) {
 166                     newVar = new BoundVar(var.getType());
 167                     oldVarsList.add(var);
 168                     newVarsList.add(newVar);
 169                     varMap.put(var, newVar);
 170                 }
 171                 ref.replaceBy(newVar);
 172             }
 173             Constant constant = firstClosure.liftClosure(newTarget, newVarsList.toArray(new BoundVar[newVarsList.size()]));
 174             new LetApply(targets.iterator().next(), Types.PROC, constant.createOccurrence(), ValRef.createOccurrences(oldVarsList))
 175             .insertBefore(this);
 176             detach();
 177             context.addClosure(firstClosure);
 178             return;
 179         }
 180
 181         // Classify by BoundVars
 182         THashSet<BoundVar> boundVars = new THashSet<BoundVar>();
 183         ArrayList<BoundVar> boundVarsList = new ArrayList<BoundVar>(4);
 184         ArrayList<ValRef> newFreeVars = new ArrayList<ValRef>(freeVars.size());
 185         for(ValRef ref : freeVars) {
 186             BoundVar var = (BoundVar)ref.getBinding();
 187             if(targets.contains(var)) {
 188                 isRecursive = true;
 189                 continue;
 190             }
 191             if(boundVars.add(var))
 192                 boundVarsList.add(var);
 193             newFreeVars.add(ref);
 194         }
 195         BoundVar[] outVars = boundVarsList.toArray(new BoundVar[boundVarsList.size()]);
 196         freeVars = newFreeVars;
 197
 198         // Modify functions
 199         THashMap<SSAClosure, THashMap<BoundVar, BoundVar>> varMap = new THashMap<SSAClosure, THashMap<BoundVar, BoundVar>>();
 200         THashMap<SSAClosure, BoundVar[]> inVarsMap = new THashMap<SSAClosure, BoundVar[]>();
 201         THashMap<SSAClosure, BoundVar> oldTargets = new THashMap<SSAClosure, BoundVar>();
 202         for(SSAClosure closure = firstClosure;
 203                 closure != null;
 204                 closure = closure.getNext()) {
 205             THashMap<BoundVar, BoundVar> map = new THashMap<BoundVar, BoundVar>(outVars.length);
 206             BoundVar[] inVars = new BoundVar[outVars.length];
 207             for(int i=0;i<inVars.length;++i) {
 208                 inVars[i] = new BoundVar(outVars[i].getType());
 209                 map.put(outVars[i], inVars[i]);
 210             }
 211             inVarsMap.put(closure, inVars);
 212             varMap.put(closure, map);
 213
 214             closure.parametrize(inVars);
 215             SCLConstant functionConstant = new SCLConstant(context.createName(), closure.getType());
 216             context.addConstant(functionConstant);
 217             oldTargets.put(closure, (BoundVar)closure.getTarget());
 218             closure.setTarget(functionConstant);
 219             functionConstant.setDefinition((SSAFunction)closure);
 220             functionConstant.setPrivate(true);
 221             // TODO handle type parameters
 222
 223             // Define target by an application
 224             /*new LetApply(oldTarget, functionConstant.createOccurrence(),
 225                     ValRef.createOccurrences(outVars)).insertBefore(this);*/
 226         }
 227
 228         for(SSAClosure closure = firstClosure;
 229                 closure != null;
 230                 closure = closure.getNext()) {
 231             BoundVar oldTarget = oldTargets.get(closure);
 232             for(ValRef ref : oldTarget.getOccurences()) {
 233                 SSAFunction parent = ref.getParentFunction();
 234                 BoundVar[] vars = inVarsMap.get(parent);
 235                 if(vars == null)
 236                     vars = outVars;
 237                 if(vars.length > 0)
 238                     ref.replaceByApply(closure.getTarget(), vars);
 239                 else
 240                     ref.replaceBy(closure.getTarget());
 241             }
 242         }
 243
 244         // Fix references
 245         for(ValRef ref : freeVars) {
 246             BoundVar inVar = (BoundVar)ref.getBinding();
 247             if(targets.contains(inVar))
 248                 continue;
 249             BoundVar outVar = varMap.get(ref.getParentFunction()).get(inVar);
 250             ref.replaceBy(outVar);
 251         }
 252
 253         detach();
 254         //context.validate();
 255
 256         if(hasValues && isRecursive)
 257             context.getErrorLog().log(recursiveGroupLocation, "Variables defined recursively must all be functions.");
 258     }
 259
 260     @Override
 261     public void simplify(SSASimplificationContext context) {
 262         for(SSAClosure function = firstClosure;
 263                 function != null;
 264                 function = function.getNext())
 265             function.simplify(context);
 266     }
 267
 268     public void setRecursiveGroupLocation(long recursiveGroupLocation) {
 269         this.recursiveGroupLocation = recursiveGroupLocation;
 270     }
 271
 272     @Override
 273     public void forValRefs(ValRefVisitor visitor) {
 274         for(SSAClosure closure = firstClosure; closure != null; closure = closure.getNext())
 275             closure.forValRefs(visitor);
 276     }
 277 }