001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.jikesrvm.compilers.opt.controlflow;
014
015import java.util.Enumeration;
016import java.util.HashMap;
017import java.util.Map;
018
019import org.jikesrvm.compilers.opt.OperationNotImplementedException;
020import org.jikesrvm.compilers.opt.dfsolver.DF_LatticeCell;
021import org.jikesrvm.compilers.opt.dfsolver.DF_Solution;
022import org.jikesrvm.compilers.opt.ir.BasicBlock;
023import org.jikesrvm.compilers.opt.ir.IR;
024
025/**
026 * Calculate dominators for basic blocks.
027 * <p> Uses the algorithm contained in Dragon book, pg. 670-1.
028 * <pre>
029 *       D(n0) := { n0 }
030 *       for n in N - { n0 } do D(n) := N;
031 *       while changes to any D(n) occur do
032 *         for n in N - {n0} do
033 *             D(n) := {n} U (intersect of D(p) over all predecessors p of n)
034 * </pre>
035 * <p> TODO: we do not support IRs with exception handlers!!
036 */
037public class Dominators {
038  /**
039   * Control for debug output
040   */
041  static final boolean DEBUG = false;
042  /**
043   * Should we compute post-dominators instead of dominators? This is
044   * false by default.
045   */
046  static boolean COMPUTE_POST_DOMINATORS = false;
047
048  private Map<BasicBlock, DominatorInfo> dominatorInfo;
049
050  /**
051   * Calculate the dominators for an IR.
052   *
053   * @param ir the IR in question
054   */
055  public void perform(IR ir) {
056    if (ir.hasReachableExceptionHandlers()) {
057      throw new OperationNotImplementedException("IR with exception handlers");
058    }
059    DominatorSystem system = new DominatorSystem(ir);
060    if (DEBUG) {
061      System.out.print("Solving...");
062    }
063    if (DEBUG) {
064      System.out.println(system);
065    }
066    system.solve();
067    if (DEBUG) {
068      System.out.println("done");
069    }
070    DF_Solution solution = system.getSolution();
071    if (DEBUG) {
072      System.out.println("Dominator Solution :" + solution);
073    }
074    if (DEBUG) {
075      System.out.print("Updating blocks ...");
076    }
077    updateBlocks(solution);
078    if (DEBUG) {
079      System.out.println("done.");
080    }
081    if (ir.options.PRINT_DOMINATORS) {
082      printDominators(ir);
083    }
084  }
085
086  /**
087   * Calculate the "approximate" dominators for an IR i.e., the
088   * dominators in the factored CFG rather than the normal CFG.
089   * <p> (No exception is thrown if the input IR has handler blocks.)
090   *
091   * @param ir the IR in question
092   */
093  public void computeApproxDominators(IR ir) {
094    DominatorSystem system = new DominatorSystem(ir);
095    if (DEBUG) {
096      System.out.print("Solving...");
097    }
098    if (DEBUG) {
099      System.out.println(system);
100    }
101    system.solve();
102    if (DEBUG) {
103      System.out.println("done");
104    }
105    DF_Solution solution = system.getSolution();
106    if (DEBUG) {
107      System.out.println("Dominator Solution :" + solution);
108    }
109    if (DEBUG) {
110      System.out.print("Updating blocks ...");
111    }
112    updateBlocks(solution);
113    if (DEBUG) {
114      System.out.println("done.");
115    }
116    if (ir.options.PRINT_DOMINATORS) {
117      printDominators(ir);
118    }
119  }
120
121  /**
122   * Calculate the postdominators for an IR.
123   *
124   * @param ir the IR in question
125   */
126  public void computeApproxPostdominators(IR ir) {
127    Dominators.COMPUTE_POST_DOMINATORS = true;
128    DominatorSystem system = new DominatorSystem(ir);
129    if (DEBUG) {
130      System.out.print("Solving...");
131    }
132    if (DEBUG) {
133      System.out.println(system);
134    }
135    system.solve();
136    if (DEBUG) {
137      System.out.println("done");
138    }
139    DF_Solution solution = system.getSolution();
140    if (DEBUG) {
141      System.out.println("Postdominator Solution :" + solution);
142    }
143    if (DEBUG) {
144      System.out.print("Updating blocks ...");
145    }
146    updateBlocks(solution);
147    if (DEBUG) {
148      System.out.println("done.");
149    }
150    if (ir.options.PRINT_DOMINATORS) {
151      printDominators(ir);
152    }
153    Dominators.COMPUTE_POST_DOMINATORS = false;
154  }
155
156  /**
157   * Creates a {@code DominatorInfo} for each basic block
158   * in the data flow system solution.
159   *
160   * @param solution the solution to the Dominators equations
161   */
162  public void updateBlocks(DF_Solution solution) {
163    int capacityToPreventRehash = (int) (solution.size() * 1.4f);
164    dominatorInfo = new HashMap<BasicBlock, DominatorInfo>(capacityToPreventRehash);
165    for (final DF_LatticeCell latticeCell : solution.values()) {
166      DominatorCell cell = (DominatorCell) latticeCell;
167      BasicBlock b = cell.block;
168      dominatorInfo.put(b, new DominatorInfo(cell.dominators));
169      if (DEBUG) {
170        System.out.println("Dominators of " + b + ":" + cell.dominators);
171      }
172    }
173  }
174
175  /**
176   * Print the (already calculated) dominators.
177   * @param ir the IR
178   */
179  public void printDominators(IR ir) {
180    for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
181      BasicBlock b = e.nextElement();
182      DominatorInfo i = dominatorInfo.get(b);
183      System.out.println("Dominators of " + b + ":" + i.dominators);
184    }
185  }
186
187  public DominatorInfo getDominatorInfo(BasicBlock b) {
188    return dominatorInfo.get(b);
189  }
190}