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                     newVar.setLabel(var.getLabel());
 168                     oldVarsList.add(var);
 169                     newVarsList.add(newVar);
 170                     varMap.put(var, newVar);
 171                 }
 172                 ref.replaceBy(newVar);
 173             }
 174             Constant constant = firstClosure.liftClosure(newTarget, newVarsList.toArray(new BoundVar[newVarsList.size()]));
 175             new LetApply(targets.iterator().next(), Types.PROC, constant.createOccurrence(), ValRef.createOccurrences(oldVarsList))
 176             .insertBefore(this);
 177             detach();
 178             context.addClosure(firstClosure);
 179             return;
 180         }
 181
 182         // Classify by BoundVars
 183         THashSet<BoundVar> boundVars = new THashSet<BoundVar>();
 184         ArrayList<BoundVar> boundVarsList = new ArrayList<BoundVar>(4);
 185         ArrayList<ValRef> newFreeVars = new ArrayList<ValRef>(freeVars.size());
 186         for(ValRef ref : freeVars) {
 187             BoundVar var = (BoundVar)ref.getBinding();
 188             if(targets.contains(var)) {
 189                 isRecursive = true;
 190                 continue;
 191             }
 192             if(boundVars.add(var))
 193                 boundVarsList.add(var);
 194             newFreeVars.add(ref);
 195         }
 196         BoundVar[] outVars = boundVarsList.toArray(new BoundVar[boundVarsList.size()]);
 197         freeVars = newFreeVars;
 198
 199         // Modify functions
 200         THashMap<SSAClosure, THashMap<BoundVar, BoundVar>> varMap = new THashMap<SSAClosure, THashMap<BoundVar, BoundVar>>();
 201         THashMap<SSAClosure, BoundVar[]> inVarsMap = new THashMap<SSAClosure, BoundVar[]>();
 202         THashMap<SSAClosure, BoundVar> oldTargets = new THashMap<SSAClosure, BoundVar>();
 203         for(SSAClosure closure = firstClosure;
 204                 closure != null;
 205                 closure = closure.getNext()) {
 206             THashMap<BoundVar, BoundVar> map = new THashMap<BoundVar, BoundVar>(outVars.length);
 207             BoundVar[] inVars = new BoundVar[outVars.length];
 208             for(int i=0;i<inVars.length;++i) {
 209                 inVars[i] = new BoundVar(outVars[i].getType());
 210                 map.put(outVars[i], inVars[i]);
 211             }
 212             inVarsMap.put(closure, inVars);
 213             varMap.put(closure, map);
 214
 215             closure.parametrize(inVars);
 216             SCLConstant functionConstant = new SCLConstant(context.createName(), closure.getType());
 217             context.addConstant(functionConstant);
 218             oldTargets.put(closure, (BoundVar)closure.getTarget());
 219             closure.setTarget(functionConstant);
 220             functionConstant.setDefinition((SSAFunction)closure);
 221             functionConstant.setPrivate(true);
 222             // TODO handle type parameters
 223
 224             // Define target by an application
 225             /*new LetApply(oldTarget, functionConstant.createOccurrence(),
 226                     ValRef.createOccurrences(outVars)).insertBefore(this);*/
 227         }
 228
 229         for(SSAClosure closure = firstClosure;
 230                 closure != null;
 231                 closure = closure.getNext()) {
 232             BoundVar oldTarget = oldTargets.get(closure);
 233             for(ValRef ref : oldTarget.getOccurences()) {
 234                 SSAFunction parent = ref.getParentFunction();
 235                 BoundVar[] vars = inVarsMap.get(parent);
 236                 if(vars == null)
 237                     vars = outVars;
 238                 if(vars.length > 0)
 239                     ref.replaceByApply(closure.getTarget(), vars);
 240                 else
 241                     ref.replaceBy(closure.getTarget());
 242             }
 243         }
 244
 245         // Fix references
 246         for(ValRef ref : freeVars) {
 247             BoundVar inVar = (BoundVar)ref.getBinding();
 248             if(targets.contains(inVar))
 249                 continue;
 250             BoundVar outVar = varMap.get(ref.getParentFunction()).get(inVar);
 251             ref.replaceBy(outVar);
 252         }
 253
 254         detach();
 255         //context.validate();
 256
 257         if(hasValues && isRecursive)
 258             context.getErrorLog().log(recursiveGroupLocation, "Variables defined recursively must all be functions.");
 259     }
 260
 261     @Override
 262     public void simplify(SSASimplificationContext context) {
 263         for(SSAClosure function = firstClosure;
 264                 function != null;
 265                 function = function.getNext())
 266             function.simplify(context);
 267     }
 268
 269     public void setRecursiveGroupLocation(long recursiveGroupLocation) {
 270         this.recursiveGroupLocation = recursiveGroupLocation;
 271     }
 272
 273     @Override
 274     public void forValRefs(ValRefVisitor visitor) {
 275         for(SSAClosure closure = firstClosure; closure != null; closure = closure.getNext())
 276             closure.forValRefs(visitor);
 277     }
 278 }