bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/codegen/analysis/Dominance.java

   1 package org.simantics.scl.compiler.internal.codegen.analysis;\r
   2 \r
   3 public abstract class Dominance {\r
   4 \r
   5     int[] idom;\r
   6     \r
   7     public Dominance(int size) {\r
   8         idom = new int[size];\r
   9         idom[0] = 0;\r
  10         for(int i=1;i<size;++i)\r
  11             idom[i] = -1;\r
  12     }\r
  13     \r
  14     public void compute() {\r
  15         boolean changed;\r
  16         do {\r
  17             changed = true;\r
  18             for(int i=1;i<idom.length;++i) {\r
  19                 int curDom = -1;\r
  20                 for(int pred : predecessors(i)) {\r
  21                     int dom = idom[pred];\r
  22                     if(dom >= 0) {\r
  23                         if(curDom < 0)\r
  24                             curDom = dom;\r
  25                         else\r
  26                             curDom = intersect(dom, curDom);\r
  27                     }\r
  28                 }\r
  29                 if(idom[i] != curDom) {\r
  30                     idom[i] = curDom;\r
  31                     changed = true;\r
  32                 }\r
  33             }\r
  34         } while(changed);\r
  35     }\r
  36     \r
  37     private int intersect(int a, int b) {\r
  38         while(a != b) {\r
  39             if(a < b)\r
  40                 b = idom[b];\r
  41             else\r
  42                 a = idom[a];\r
  43         }\r
  44         return a;\r
  45     }\r
  46 \r
  47     protected abstract int[] predecessors(int i);\r
  48     \r
  49 }\r