From 51a4b7a930406a4890258f598661edc4b44e181a Mon Sep 17 00:00:00 2001 From: =?utf8?q?Hannu=20Niemist=C3=B6?= Date: Mon, 20 Feb 2017 11:17:31 +0200 Subject: [PATCH] (refs #7042) Added a new compiler optimization (eta-reduce) Adds new optimization to SCL compiler that transforms the following code \someParameters = f someOtherParameters someParameters' to f someOtherParameters with the following restrictions: * someParameters and someParameters' are lists of equal variables or the type is () * someOtherParameters does not refer to variables in someParameters or the lambda expression itself or something depending on it recursively [PRIVATE-13082] Change-Id: I0e666771c72128ab73b0e46af727236ba4811080 --- .../internal/codegen/ssa/SSAFunction.java | 85 ++++++++++++++++++- .../internal/codegen/ssa/exits/Switch.java | 7 +- .../scl/compiler/tests/ActiveTests.java | 5 +- .../compiler/tests/ModuleRegressionTests.java | 2 + .../compiler/tests/scl/ClosureRecursion.scl | 21 +++++ .../tests/scl/SwitchSimplification.scl | 5 ++ 6 files changed, 116 insertions(+), 9 deletions(-) create mode 100644 tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/ClosureRecursion.scl create mode 100644 tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/SwitchSimplification.scl diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/SSAFunction.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/SSAFunction.java index 68dd82f15..ab643f9a1 100644 --- a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/SSAFunction.java +++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/SSAFunction.java @@ -5,6 +5,7 @@ import java.util.Arrays; import org.cojen.classfile.TypeDesc; import org.simantics.scl.compiler.common.exceptions.InternalCompilerError; +import org.simantics.scl.compiler.constants.NoRepConstant; 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.continuations.ReturnCont; @@ -173,12 +174,88 @@ public final class SSAFunction extends SSAClosure { public void simplify(SSASimplificationContext context) { for(SSABlock block = firstBlock; block != null; block = block.next) block.simplify(context); - if(firstBlock == lastBlock && firstBlock.firstStatement == firstBlock.lastStatement && - firstBlock.firstStatement instanceof LetFunctions) { - simplifySingleLambda(context); + if(firstBlock == lastBlock && firstBlock.firstStatement == firstBlock.lastStatement) { + if(firstBlock.firstStatement instanceof LetApply) + simplifySingleApply(context); + else if(firstBlock.firstStatement instanceof LetFunctions) + simplifySingleLambda(context); } } + + /** + * Simplifies the following kind of function definition + * \x -> f x + * to + * f + */ + private void simplifySingleApply(SSASimplificationContext context) { + if(!(parent instanceof LetFunctions) || parent.getFirstClosure().next != null) + return; + LetApply apply = (LetApply)firstBlock.firstStatement; + if(!(firstBlock.exit instanceof Jump)) + return; + Jump exit = (Jump)firstBlock.exit; + if(exit.getTarget().getBinding() != returnCont) + return; + if(exit.getParameter(0).getBinding() != apply.getTarget()) + return; + BoundVar[] functionParameters = getParameters(); + ValRef[] applyParameters = apply.getParameters(); + if(functionParameters.length > applyParameters.length) + return; + int extraApplyParameters = applyParameters.length - functionParameters.length; + for(int i=0;i 0) { + //System.out.println("-------------------------------------------------------------"); + //System.out.println(parentFunction); + //System.out.println("-------------------------------------------------------------"); + apply.setTarget((BoundVar)target); + apply.setParameters(Arrays.copyOf(applyParameters, extraApplyParameters)); + apply.insertBefore(binder); + binder.detach(); + //System.out.println(parentFunction); + //System.out.println("-------------------------------------------------------------"); + } + else { + binder.detach(); + ((BoundVar)target).replaceBy(apply.getFunction()); + } + context.markModified("SSAFunction.eta-reduce"); + } + + private boolean representSameValues(BoundVar boundVar, ValRef valRef) { + Val val = valRef.getBinding(); + if(val == boundVar && valRef.getTypeParameters().length == 0) + return true; + if(val instanceof NoRepConstant && Types.equals(valRef.getType(), boundVar.getType())) + return true; + return false; + } + + /** + * Simplifies the following kind of function definition + * \x -> \y -> e + * to + * \x y -> e + */ private void simplifySingleLambda(SSASimplificationContext context) { LetFunctions letF = (LetFunctions)firstBlock.firstStatement; if(!(letF.getFirstClosure() instanceof SSAFunction)) @@ -202,7 +279,7 @@ public final class SSAFunction extends SSAClosure { lastBlock = f.lastBlock; firstBlock.firstStatement = firstBlock.lastStatement = null; - setReturnCont(f.getReturnCont()); + setReturnCont(f.getReturnCont()); effect = f.effect; BoundVar[] newParameters = BoundVar.copy(f.firstBlock.parameters); firstBlock.setParameters(BoundVar.concat(getParameters(), newParameters)); diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/exits/Switch.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/exits/Switch.java index 0bcb3dd59..27f853e02 100644 --- a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/exits/Switch.java +++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/exits/Switch.java @@ -6,6 +6,7 @@ import org.objectweb.asm.Label; import org.simantics.scl.compiler.common.exceptions.InternalCompilerError; import org.simantics.scl.compiler.constants.BooleanConstant; import org.simantics.scl.compiler.constants.IntegerConstant; +import org.simantics.scl.compiler.constants.NoRepConstant; 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; @@ -223,11 +224,15 @@ public class Switch extends SSAExit implements ValRefBinder { context.markModified("switch-to-if"); newExit.simplify(context); } - else if(branches.length == 1 && branches[0].constructor == null) { + else if(branches.length == 1 && isConstructorParameterless(branches[0])) { scrutinee.remove(); getParent().setExit(new Jump(branches[0].cont)); } } + + private static boolean isConstructorParameterless(BranchRef branch) { + return branch.constructor == null || branch.constructor instanceof NoRepConstant; + } @Override public void collectFreeVariables(SSAFunction function, diff --git a/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ActiveTests.java b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ActiveTests.java index 4670b048d..82193b481 100644 --- a/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ActiveTests.java +++ b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ActiveTests.java @@ -1,7 +1,5 @@ package org.simantics.scl.compiler.tests; -import org.junit.Test; - public class ActiveTests extends TestBase { public ActiveTests() { super("scl"); } @@ -18,7 +16,6 @@ public class ActiveTests extends TestBase { @Test public void TypeClassBug2() { test(); } */ - //@Test public void CityoptSetup() { test(); } + //@Test public void Bug6989() { test(); } - @Test public void Bug6989() { test(); } } diff --git a/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ModuleRegressionTests.java b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ModuleRegressionTests.java index 38506c6f4..7843bac52 100644 --- a/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ModuleRegressionTests.java +++ b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/ModuleRegressionTests.java @@ -26,6 +26,7 @@ public class ModuleRegressionTests extends TestBase { @Test public void CHR2() { test(); } @Test public void CHR3() { test(); } @Test public void CHR4() { test(); } + @Test public void ClosureRecursion() { test(); } @Test public void Collaz() { test(); } @Test public void Compose() { test(); } @Test public void Composition() { test(); } @@ -224,6 +225,7 @@ public class ModuleRegressionTests extends TestBase { @Test public void StringInterpolation3() { test(); } @Test public void StringMatching1() { test(); } @Test public void SumOfInverses2() { test(); } + @Test public void SwitchSimplification() { test(); } @Test public void TooManyParametersToSin() { test(); } @Test public void Transformation1() { test(); } @Test public void Transformation2() { test(); } diff --git a/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/ClosureRecursion.scl b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/ClosureRecursion.scl new file mode 100644 index 000000000..4b31b1d2f --- /dev/null +++ b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/ClosureRecursion.scl @@ -0,0 +1,21 @@ +import "Prelude" + +countDown :: Ref Integer -> Boolean +countDown r = if currentValue <= 0 + then False + else do + r := currentValue - 1 + True + where + currentValue = getRef r + +strangeLoop :: ( Boolean) -> () +strangeLoop cond = if cond + then strangeLoop cond + else () + +main = do + r = ref 100000 :: Ref Integer + strangeLoop (countDown r) +-- +() \ No newline at end of file diff --git a/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/SwitchSimplification.scl b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/SwitchSimplification.scl new file mode 100644 index 000000000..8ea1d0128 --- /dev/null +++ b/tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/SwitchSimplification.scl @@ -0,0 +1,5 @@ +foo () = "asd" + +main = foo () +-- +asd \ No newline at end of file -- 2.43.2