Migrated source code from Simantics SVN

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

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/Dominance.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/Dominance.java
new file mode 100644 (file)
index 0000000..73e2349
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/Dominance.java
@@ -0,0 +1,49 @@
+package org.simantics.scl.compiler.internal.codegen.analysis;\r
+\r
+public abstract class Dominance {\r
+\r
+    int[] idom;\r
+    \r
+    public Dominance(int size) {\r
+        idom = new int[size];\r
+        idom[0] = 0;\r
+        for(int i=1;i<size;++i)\r
+            idom[i] = -1;\r
+    }\r
+    \r
+    public void compute() {\r
+        boolean changed;\r
+        do {\r
+            changed = true;\r
+            for(int i=1;i<idom.length;++i) {\r
+                int curDom = -1;\r
+                for(int pred : predecessors(i)) {\r
+                    int dom = idom[pred];\r
+                    if(dom >= 0) {\r
+                        if(curDom < 0)\r
+                            curDom = dom;\r
+                        else\r
+                            curDom = intersect(dom, curDom);\r
+                    }\r
+                }\r
+                if(idom[i] != curDom) {\r
+                    idom[i] = curDom;\r
+                    changed = true;\r
+                }\r
+            }\r
+        } while(changed);\r
+    }\r
+    \r
+    private int intersect(int a, int b) {\r
+        while(a != b) {\r
+            if(a < b)\r
+                b = idom[b];\r
+            else\r
+                a = idom[a];\r
+        }\r
+        return a;\r
+    }\r
+\r
+    protected abstract int[] predecessors(int i);\r
+    \r
+}\r