From 1a1bd2744cf9615f1cc7364094c5d9bdbdd4c97f Mon Sep 17 00:00:00 2001 From: =?utf8?q?Hannu=20Niemist=C3=B6?= Date: Wed, 15 Mar 2017 10:46:21 +0200 Subject: [PATCH] (refs #7088) Improvements to tail call optimization Change-Id: I7e6b914c239b1aa81a06ad9da2cdbf046ac5e0e2 --- .../internal/codegen/ssa/SSABlock.java | 109 +++++++++++++----- .../internal/codegen/utils/SSAUtils.java | 31 +++++ 2 files changed, 114 insertions(+), 26 deletions(-) create mode 100644 bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/utils/SSAUtils.java diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/SSABlock.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/SSABlock.java index c9f33ec50..aaab03e1a 100644 --- a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/SSABlock.java +++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/ssa/SSABlock.java @@ -4,6 +4,7 @@ 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; @@ -21,6 +22,7 @@ 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; @@ -281,27 +283,42 @@ public final class SSABlock extends Cont implements Printable, BoundVarBinder { 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]; - 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; + 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(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); } - if(constant == null) - return false; // This is a strange case, because we cannot get the parameter anywhere - parameter.replaceBy(constantRef); for(ContRef ref = getOccurrence(); ref != null; ref = ref.getNext()) { Jump jump = (Jump)ref.getParent(); @@ -331,32 +348,72 @@ public final class SSABlock extends Cont implements Printable, BoundVarBinder { return result; } + /* + * This method assumes that the exit of the block is Jump. + */ private boolean optimizeTailSelfCall() { - Jump jump = (Jump)exit; - if(jump.getTarget().getBinding() != parent.returnCont) - return false; - if(jump.getParameters().length != 1) - return false; + // 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; - SSABlock initialBlock = parent.firstBlock; - if(initialBlock.parameters.length != apply.getParameters().length) - return false; 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> AFTER INLINE >>"); System.out.println(getParent()); diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/utils/SSAUtils.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/utils/SSAUtils.java new file mode 100644 index 000000000..7de1ab4e6 --- /dev/null +++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/utils/SSAUtils.java @@ -0,0 +1,31 @@ +package org.simantics.scl.compiler.internal.codegen.utils; + +import org.simantics.scl.compiler.internal.codegen.references.Val; +import org.simantics.scl.compiler.internal.codegen.references.ValRef; +import org.simantics.scl.compiler.types.Type; +import org.simantics.scl.compiler.types.Types; + +public class SSAUtils { + + public static boolean representSameValue(Val a, ValRef b) { + if(b.getTypeParameters().length > 0) + return false; + return representSameValue(a, b.getBinding()); + } + + public static boolean representSameValue(Val a, Val b) { + if(a == b) + return true; + Type aT = a.getType(); + Type bT = b.getType(); + if(!Types.equals(aT, bT)) + return false; + return isSingletonType(aT); + } + + public static boolean isSingletonType(Type type) { + type = Types.canonical(type); + return type == Types.UNIT || type == Types.PUNIT; + } + +} -- 2.43.2