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