X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Fcodegen%2Fanalysis%2FLoopAnalysis.java;fp=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Fcodegen%2Fanalysis%2FLoopAnalysis.java;h=9d6a5645ac1b52cd8bff29da183ea7b9bdb30d35;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/LoopAnalysis.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/LoopAnalysis.java
new file mode 100644
index 000000000..9d6a5645a
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/LoopAnalysis.java
@@ -0,0 +1,90 @@
+package org.simantics.scl.compiler.internal.codegen.analysis;
+
+import gnu.trove.set.hash.THashSet;
+
+import org.simantics.scl.compiler.common.names.Name;
+import org.simantics.scl.compiler.constants.SCLConstant;
+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.SSABlock;
+import org.simantics.scl.compiler.internal.codegen.ssa.SSAFunction;
+import org.simantics.scl.compiler.internal.codegen.ssa.binders.ValRefBinder;
+import org.simantics.scl.compiler.internal.codegen.ssa.statements.LetApply;
+
+public class LoopAnalysis {
+
+    /**
+     * Checks if it is possible to return to the loop after exiting 
+     * before exiting the function where the block belongs to.
+     */
+    private static boolean isLoopingBlock(SSABlock block) {
+        THashSet<SSABlock> handled = new THashSet<SSABlock>();
+        for(SSABlock succBlock : block.getExit().getSuccessors())
+            if(isLoopingBlock(block, handled, succBlock))
+                return true;
+        return false;
+    }
+
+    /**
+     * Checks if it is possible to execute block more than once without visiting
+     * the breaker block. It is assumed that breaker is a dominator of the block.
+     */
+    public static boolean isLoopingBlockWithBreaker(SSABlock block, SSABlock breaker) {
+        SSAFunction function = block.getParent();
+        
+        if(function == block.getParent()) {            
+            THashSet<SSABlock> handled = new THashSet<SSABlock>();
+            handled.add(breaker);
+            for(SSABlock succBlock : block.getExit().getSuccessors())
+                if(isLoopingBlock(block, handled, succBlock))
+                    return true;
+            return false;
+        }
+        else {
+            if(isLoopingBlock(block))
+                return false;
+            Val functionTarget = function.getTarget();
+            if(functionTarget.hasMoreThanOneOccurences())
+                return false;
+            ValRef occ = functionTarget.getOccurrence();
+            if(occ == null)
+                return false;
+            ValRefBinder occParent = occ.getParent();
+            if(!(occParent instanceof LetApply))
+                return true; // Not necessarily the right answer, but we don't try to analyse further
+            LetApply apply = (LetApply)occParent;
+            if(!isAppliedAtMostOnce(apply, occ, function))
+                return true;
+            return isLoopingBlockWithBreaker(apply.getParent(), breaker);
+        }
+    }    
+
+    private static final Name BUILD = Name.create("Prelude", "build");
+    
+    private static boolean isAppliedAtMostOnce(LetApply apply, ValRef funRef, SSAFunction function) {
+        ValRef applyFunctionRef = apply.getFunction();
+        if(funRef == applyFunctionRef) {            
+            return apply.getParameters().length == function.getArity();
+        }
+        Val applyFunction = applyFunctionRef.getBinding();
+        if(!(applyFunction instanceof SCLConstant))
+            return false; // Not necessarily the right answer
+        Name name = ((SCLConstant)applyFunction).getName();
+        if(name == BUILD)
+            return true;
+        return false;
+    }
+
+    private static boolean isLoopingBlock(SSABlock originalBlock,
+            THashSet<SSABlock> handled, SSABlock block) {
+        if(!handled.add(block))
+            return false;
+        if(block == originalBlock)
+            return true;
+        for(SSABlock succBlock : block.getExit().getSuccessors())
+            if(isLoopingBlock(originalBlock, handled, succBlock))
+                return true;
+        return false;
+    }
+    
+}