--- /dev/null
+package org.simantics.scl.compiler.internal.codegen.ssa;\r
+\r
+import java.util.ArrayList;\r
+\r
+import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;\r
+import org.simantics.scl.compiler.constants.Constant;\r
+import org.simantics.scl.compiler.constants.SCLConstant;\r
+import org.simantics.scl.compiler.internal.codegen.continuations.BranchRef;\r
+import org.simantics.scl.compiler.internal.codegen.continuations.Cont;\r
+import org.simantics.scl.compiler.internal.codegen.continuations.ContRef;\r
+import org.simantics.scl.compiler.internal.codegen.references.BoundVar;\r
+import org.simantics.scl.compiler.internal.codegen.references.Val;\r
+import org.simantics.scl.compiler.internal.codegen.references.ValRef;\r
+import org.simantics.scl.compiler.internal.codegen.ssa.binders.BoundVarBinder;\r
+import org.simantics.scl.compiler.internal.codegen.ssa.exits.Jump;\r
+import org.simantics.scl.compiler.internal.codegen.ssa.exits.Switch;\r
+import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;\r
+import org.simantics.scl.compiler.internal.codegen.utils.CopyContext;\r
+import org.simantics.scl.compiler.internal.codegen.utils.MethodBuilder;\r
+import org.simantics.scl.compiler.internal.codegen.utils.Printable;\r
+import org.simantics.scl.compiler.internal.codegen.utils.PrintingContext;\r
+import org.simantics.scl.compiler.internal.codegen.utils.SSALambdaLiftingContext;\r
+import org.simantics.scl.compiler.internal.codegen.utils.SSASimplificationContext;\r
+import org.simantics.scl.compiler.internal.codegen.utils.SSAValidationContext;\r
+import org.simantics.scl.compiler.top.SCLCompilerConfiguration;\r
+import org.simantics.scl.compiler.types.TVar;\r
+import org.simantics.scl.compiler.types.Type;\r
+import org.simantics.scl.compiler.types.Types;\r
+\r
+public final class SSABlock extends Cont implements Printable, BoundVarBinder {\r
+ public static final SSABlock[] EMPTY_ARRAY = new SSABlock[0];\r
+ \r
+ BoundVar[] parameters;\r
+ \r
+ SSAFunction parent;\r
+ SSABlock prev;\r
+ SSABlock next;\r
+ SSAStatement firstStatement;\r
+ SSAStatement lastStatement;\r
+ SSAExit exit;\r
+ \r
+ public SSABlock(Type ... parameterTypes) {\r
+ parameters = new BoundVar[parameterTypes.length];\r
+ for(int i=0;i<parameterTypes.length;++i) {\r
+ BoundVar parameter = new BoundVar(parameterTypes[i]); \r
+ parameters[i] = parameter;\r
+ parameter.parent = this;\r
+ }\r
+ }\r
+ \r
+ public SSABlock(BoundVar[] parameters) { \r
+ this.parameters = parameters;\r
+ for(BoundVar parameter : parameters)\r
+ parameter.parent = this;\r
+ }\r
+\r
+ public SSAFunction getParent() {\r
+ return parent;\r
+ }\r
+ \r
+ public SSABlock getNext() {\r
+ return next;\r
+ }\r
+ \r
+ public SSABlock getPrev() {\r
+ return prev;\r
+ }\r
+ \r
+ public SSAExit getExit() {\r
+ return exit;\r
+ }\r
+ \r
+ public void removeStatements() {\r
+ this.firstStatement = null;\r
+ this.lastStatement = null; \r
+ }\r
+ \r
+ @Override\r
+ public int getArity() {\r
+ return parameters.length;\r
+ }\r
+ \r
+ public int getStatementCount() {\r
+ int count = 0;\r
+ for(SSAStatement stat = firstStatement;stat != null;stat = stat.next)\r
+ ++count;\r
+ return count;\r
+ }\r
+ \r
+ @Override\r
+ public Type getParameterType(int parameterId) {\r
+ return parameters[parameterId].getType();\r
+ }\r
+ \r
+ public Type[] getParameterTypes() {\r
+ return Types.getTypes(parameters);\r
+ }\r
+ \r
+ public BoundVar[] getParameters() {\r
+ return parameters;\r
+ }\r
+ \r
+ public void setExit(SSAExit exit) {\r
+ this.exit = exit;\r
+ exit.parent = this;\r
+ }\r
+\r
+ public void detach() {\r
+ if(prev == null)\r
+ parent.firstBlock = next;\r
+ else\r
+ prev.next = next;\r
+ if(next == null)\r
+ parent.lastBlock = prev;\r
+ else\r
+ next.prev = prev;\r
+ if(parent.firstBlock == null)\r
+ throw new InternalCompilerError();\r
+ }\r
+\r
+ public void remove() {\r
+ detach();\r
+ destroy();\r
+ }\r
+ \r
+ public void destroy() {\r
+ for(SSAStatement statement = firstStatement; statement != null; statement = statement.next)\r
+ statement.destroy();\r
+ exit.destroy();\r
+ }\r
+\r
+ public void addStatement(SSAStatement stat) {\r
+ if(SCLCompilerConfiguration.DEBUG) {\r
+ if((firstStatement == null) != (lastStatement == null))\r
+ throw new InternalCompilerError();\r
+ }\r
+ stat.parent = this;\r
+ if(lastStatement == null) {\r
+ firstStatement = lastStatement = stat;\r
+ stat.next = stat.prev = null; \r
+ }\r
+ else {\r
+ lastStatement.next = stat;\r
+ stat.prev = lastStatement;\r
+ stat.next = null;\r
+ lastStatement = stat;\r
+ }\r
+ }\r
+ \r
+ public void generateCode(MethodBuilder mb) {\r
+ mb.setLocation(this);\r
+ for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)\r
+ stat.generateCode(mb);\r
+ exit.generateCode(mb);\r
+ }\r
+\r
+ public void toString(PrintingContext context) {\r
+ context.indentation();\r
+ context.append(this);\r
+ context.append("(" + occurrenceCount() + ")");\r
+ parametersToString(context);\r
+ context.append(" =\n");\r
+ bodyToString(context);\r
+ }\r
+ \r
+ public void parametersToString(PrintingContext context) {\r
+ for(BoundVar parameter : parameters) {\r
+ context.append(' ');\r
+ if(parameter.hasNoOccurences()) {\r
+ context.append('(');\r
+ context.append('_');\r
+ context.append(" :: ");\r
+ context.append(parameter.getType());\r
+ context.append(')');\r
+ }\r
+ else {\r
+ context.append('(');\r
+ context.append(parameter);\r
+ context.append(" :: ");\r
+ context.append(parameter.getType());\r
+ context.append(')');\r
+ }\r
+ }\r
+ }\r
+ \r
+ public void bodyToString(PrintingContext context) {\r
+ context.indent();\r
+ for(SSAStatement statement = firstStatement; statement != null; statement = statement.next)\r
+ statement.toString(context);\r
+ context.indentation();\r
+ exit.toString(context);\r
+ context.dedent();\r
+ }\r
+\r
+ public void validate(SSAValidationContext context) {\r
+ if(exit.getParent() != this)\r
+ throw new InternalCompilerError();\r
+ for(BoundVar parameter : parameters) { \r
+ context.validate(parameter);\r
+ if(parameter.parent != this)\r
+ throw new InternalCompilerError();\r
+ }\r
+ for(SSAStatement statement = firstStatement; statement != null; statement = statement.next) {\r
+ if(statement.getParent() != this)\r
+ throw new InternalCompilerError();\r
+ statement.validate(context);\r
+ }\r
+ exit.validate(context);\r
+ \r
+ {\r
+ SSAStatement last = firstStatement;\r
+ if(last != null) {\r
+ while(last.next != null)\r
+ last = last.next;\r
+ }\r
+ if(last != lastStatement)\r
+ throw new InternalCompilerError();\r
+ }\r
+ }\r
+\r
+ public void simplify(SSASimplificationContext context) {\r
+ if(hasNoOccurences() && parent.firstBlock != this) {\r
+ remove();\r
+ context.markModified("dead-block");\r
+ return;\r
+ }\r
+ \r
+ tryToImproveParameters(context);\r
+ \r
+ // Simplify statements and exit\r
+ for(SSAStatement statement = firstStatement; statement != null; statement = statement.next)\r
+ statement.simplify(context);\r
+ exit.simplify(context);\r
+ \r
+ // Simplifications to this block\r
+ if(exit instanceof Switch) {\r
+ if(simplifySwitch()) {\r
+ context.markModified("beta-switch");\r
+ }\r
+ }\r
+ if(exit instanceof Jump) {\r
+ if(firstStatement == null && parent.firstBlock != this) {\r
+ if(etaBlock(context)) {\r
+ context.markModified("eta-block");\r
+ return;\r
+ }\r
+ else if(inlineJump()) {\r
+ context.markModified("beta-block");\r
+ return;\r
+ }\r
+ }\r
+ else {\r
+ if(optimizeTailSelfCall()) {\r
+ context.markModified("simplify-tail-call");\r
+ return;\r
+ }\r
+ else if(inlineJump()) {\r
+ context.markModified("beta-block");\r
+ return;\r
+ }\r
+ }\r
+ } \r
+ }\r
+\r
+ private void tryToImproveParameters(SSASimplificationContext context) {\r
+ if(parent.firstBlock == this)\r
+ return;\r
+ if(parameters.length == 0)\r
+ return;\r
+ for(ContRef ref = getOccurrence(); ref != null; ref = ref.getNext())\r
+ if(!(ref.getParent() instanceof Jump))\r
+ return;\r
+ boolean modified = false;\r
+ for(int i=0;i<parameters.length;++i)\r
+ if(tryToImproveParameter(i)) {\r
+ --i;\r
+ modified = true;\r
+ }\r
+ if(modified)\r
+ context.markModified("improve-parameters");\r
+ }\r
+\r
+ private boolean tryToImproveParameter(int position) {\r
+ BoundVar parameter = parameters[position];\r
+ Val constant = null;\r
+ ValRef constantRef = null;\r
+ for(ContRef ref = getOccurrence(); ref != null; ref = ref.getNext()) {\r
+ Jump jump = (Jump)ref.getParent();\r
+ ValRef valRef = jump.getParameters()[position];\r
+ Val val = valRef.getBinding();\r
+ if(val == parameter)\r
+ continue;\r
+ if(constant == null) {\r
+ constant = val;\r
+ constantRef = valRef;\r
+ continue;\r
+ }\r
+ if(val != constant)\r
+ return false;\r
+ }\r
+ if(constant == null)\r
+ return false; // This is a strange case, because we cannot get the parameter anywhere\r
+ parameter.replaceBy(constantRef);\r
+ \r
+ for(ContRef ref = getOccurrence(); ref != null; ref = ref.getNext()) {\r
+ Jump jump = (Jump)ref.getParent();\r
+ jump.setParameters(removeAt(jump.getParameters(), position));\r
+ }\r
+ \r
+ parameters = removeAt(parameters, position);\r
+ return true;\r
+ }\r
+ \r
+ private static BoundVar[] removeAt(BoundVar[] vars, int pos) {\r
+ BoundVar[] result = new BoundVar[vars.length-1];\r
+ for(int i=0;i<pos;++i)\r
+ result[i] = vars[i];\r
+ for(int i=pos+1;i<vars.length;++i)\r
+ result[i-1] = vars[i];\r
+ return result;\r
+ }\r
+\r
+ private static ValRef[] removeAt(ValRef[] vars, int pos) {\r
+ ValRef[] result = new ValRef[vars.length-1];\r
+ for(int i=0;i<pos;++i)\r
+ result[i] = vars[i];\r
+ vars[pos].remove();\r
+ for(int i=pos+1;i<vars.length;++i)\r
+ result[i-1] = vars[i];\r
+ return result;\r
+ }\r
+ \r
+ private boolean optimizeTailSelfCall() {\r
+ Jump jump = (Jump)exit;\r
+ if(jump.getTarget().getBinding() != parent.returnCont)\r
+ return false;\r
+ if(jump.getParameters().length != 1)\r
+ return false;\r
+ if(lastStatement == null || !(lastStatement instanceof LetApply))\r
+ return false;\r
+ LetApply apply = (LetApply)lastStatement;\r
+ SSABlock initialBlock = parent.firstBlock;\r
+ if(initialBlock.parameters.length != apply.getParameters().length)\r
+ return false;\r
+ Val function = apply.getFunction().getBinding();\r
+ if(function != parent.target)\r
+ return false;\r
+ \r
+ // Do modifications\r
+ apply.detach();\r
+ apply.getFunction().remove();\r
+ jump.getTarget().remove();\r
+ jump.setTarget(initialBlock.createOccurrence());\r
+ jump.setParameters(apply.getParameters());\r
+ \r
+ return true;\r
+ }\r
+\r
+ private boolean etaBlock(SSASimplificationContext context) {\r
+ Jump jump = (Jump)exit;\r
+ if(parameters.length != jump.getParameters().length)\r
+ return false;\r
+ for(int i=0;i<parameters.length;++i)\r
+ if(parameters[i] != jump.getParameters()[i].getBinding() ||\r
+ parameters[i].hasMoreThanOneOccurences())\r
+ return false;\r
+ \r
+ replaceWith(jump.getTarget().getBinding());\r
+ remove();\r
+ return true;\r
+ }\r
+ \r
+ private boolean simplifySwitch() {\r
+ Switch sw = (Switch)exit;\r
+ ValRef scrutineeRef = sw.getScrutinee();\r
+ Val scrutinee = scrutineeRef.getBinding();\r
+ if(scrutinee instanceof BoundVar) {\r
+ BoundVarBinder parent = ((BoundVar)scrutinee).parent;\r
+ if(!(parent instanceof LetApply))\r
+ return false;\r
+ LetApply apply = (LetApply)parent;\r
+ Val function = apply.getFunction().getBinding();\r
+ if(!(function instanceof Constant) || function instanceof SCLConstant)\r
+ return false;\r
+ for(BranchRef branch : sw.getBranches()) {\r
+ if(branch.constructor == function) {\r
+ sw.destroy();\r
+ setExit(new Jump(branch.cont.getBinding().createOccurrence(), \r
+ ValRef.copy(apply.getParameters())));\r
+ return true;\r
+ }\r
+ }\r
+ }\r
+ else if(scrutinee instanceof Constant) {\r
+ if(sw.getBranches().length == 1) {\r
+ BranchRef branch = sw.getBranches()[0];\r
+ if(branch.constructor == scrutinee) {\r
+ /**\r
+ * Optimizes for example\r
+ * switch ()\r
+ * () -> [a]\r
+ * ===>\r
+ * [a]\r
+ */\r
+ sw.destroy();\r
+ setExit(new Jump(branch.cont.getBinding().createOccurrence()));\r
+ }\r
+ }\r
+ }\r
+ return false;\r
+ }\r
+ \r
+ private boolean inlineJump() {\r
+ Jump jump = (Jump)exit;\r
+ Cont target = jump.getTarget().getBinding();\r
+ if(!(target instanceof SSABlock))\r
+ return false;\r
+ if(target.hasMoreThanOneOccurences())\r
+ return false;\r
+ SSABlock block = (SSABlock)target;\r
+ if(block == parent.firstBlock || block == this)\r
+ return false;\r
+ \r
+ /*System.out.println(">> BEFORE INLINE >>");\r
+ System.out.println(getParent());\r
+ System.out.println(">> THIS BLOCK >>");\r
+ System.out.println(this);\r
+ System.out.println(">> TARGET BLOCK >>");\r
+ System.out.println(block);*/\r
+ \r
+ mergeStatements(block);\r
+\r
+ for(int i=0;i<jump.getParameters().length;++i)\r
+ block.parameters[i].replaceBy(jump.getParameters()[i]);\r
+ block.detach();\r
+ \r
+ jump.destroy();\r
+ setExit(block.exit); \r
+ \r
+ /*System.out.println(">> AFTER INLINE >>");\r
+ System.out.println(getParent());\r
+ System.out.println(">> THIS BLOCK >>");\r
+ System.out.println(this);\r
+ System.out.println(">>>>>>>>>>>>>>>>>>");*/\r
+ return true;\r
+ }\r
+ \r
+ private void mergeStatements(SSABlock block) {\r
+ if(SCLCompilerConfiguration.DEBUG) {\r
+ SSAStatement last = firstStatement;\r
+ if(last != null) {\r
+ while(last.next != null)\r
+ last = last.next;\r
+ }\r
+ if(last != lastStatement)\r
+ throw new InternalCompilerError();\r
+ }\r
+ SSAStatement stat = block.firstStatement;\r
+ while(stat != null) {\r
+ SSAStatement next = stat.next;\r
+ addStatement(stat);\r
+ stat = next;\r
+ }\r
+ }\r
+\r
+ @Override\r
+ public String toString() {\r
+ PrintingContext context = new PrintingContext();\r
+ toString(context);\r
+ return context.toString();\r
+ }\r
+\r
+ public void markGenerateOnFly() {\r
+ for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)\r
+ stat.markGenerateOnFly(); \r
+ }\r
+ \r
+ public SSABlock copy(CopyContext context) {\r
+ SSABlock newBlock = new SSABlock(context.copy(parameters));\r
+ context.put(this, newBlock);\r
+ for(SSAStatement statement = firstStatement;\r
+ statement != null; statement = statement.next)\r
+ newBlock.addStatement(statement.copy(context));\r
+ newBlock.setExit(exit.copy(context)); \r
+ return newBlock;\r
+ }\r
+\r
+ public void setParameters(BoundVar[] parameters) {\r
+ for(BoundVar parameter : parameters)\r
+ parameter.parent = this;\r
+ this.parameters = parameters;\r
+ }\r
+\r
+ @Override\r
+ public void replace(TVar[] vars, Type[] replacements) {\r
+ for(BoundVar parameter : parameters)\r
+ parameter.replace(vars, replacements);\r
+ for(SSAStatement statement = firstStatement;\r
+ statement != null; statement = statement.next)\r
+ statement.replace(vars, replacements);\r
+ exit.replace(vars, replacements);\r
+ }\r
+\r
+ public void collectFreeVariables(SSAFunction function, ArrayList<ValRef> vars) {\r
+ for(SSAStatement statement = firstStatement;\r
+ statement != null; statement = statement.next)\r
+ statement.collectFreeVariables(function, vars);\r
+ exit.collectFreeVariables(function, vars);\r
+ }\r
+\r
+ @Override\r
+ public SSAFunction getParentFunction() {\r
+ return parent;\r
+ }\r
+\r
+ public void lambdaLift(SSALambdaLiftingContext context) {\r
+ for(SSAStatement statement = firstStatement;\r
+ statement != null; statement = statement.next)\r
+ statement.lambdaLift(context);\r
+ }\r
+ \r
+ public SSAStatement getFirstStatement() {\r
+ return firstStatement;\r
+ }\r
+\r
+ public void setParameter(int position, BoundVar target) {\r
+ parameters[position] = target;\r
+ target.parent = this;\r
+ }\r
+\r
+ public void prepare(MethodBuilder mb) {\r
+ for(SSAStatement stat = firstStatement; stat != null; stat = stat.next)\r
+ stat.prepare(mb);\r
+ exit.prepare(mb);\r
+ }\r
+ \r
+}\r
Code Review / simantics / platform.git / blobdiff