Migrated source code from Simantics SVN

[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / internal / codegen / analysis / LoopAnalysis.java

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