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

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