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