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%2FDominance.java;fp=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Fcodegen%2Fanalysis%2FDominance.java;h=73e234910abcbba510c1859463a8cdbaa2bbfa56;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/Dominance.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/Dominance.java
new file mode 100644
index 000000000..73e234910
--- /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;
+
+public abstract class Dominance {
+
+    int[] idom;
+    
+    public Dominance(int size) {
+        idom = new int[size];
+        idom[0] = 0;
+        for(int i=1;i<size;++i)
+            idom[i] = -1;
+    }
+    
+    public void compute() {
+        boolean changed;
+        do {
+            changed = true;
+            for(int i=1;i<idom.length;++i) {
+                int curDom = -1;
+                for(int pred : predecessors(i)) {
+                    int dom = idom[pred];
+                    if(dom >= 0) {
+                        if(curDom < 0)
+                            curDom = dom;
+                        else
+                            curDom = intersect(dom, curDom);
+                    }
+                }
+                if(idom[i] != curDom) {
+                    idom[i] = curDom;
+                    changed = true;
+                }
+            }
+        } while(changed);
+    }
+    
+    private int intersect(int a, int b) {
+        while(a != b) {
+            if(a < b)
+                b = idom[b];
+            else
+                a = idom[a];
+        }
+        return a;
+    }
+
+    protected abstract int[] predecessors(int i);
+    
+}