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 */
013 package org.jikesrvm.compilers.opt.controlflow;
014
015 import org.jikesrvm.compilers.opt.OperationNotImplementedException;
016 import org.jikesrvm.compilers.opt.dfsolver.DF_LatticeCell;
017 import org.jikesrvm.compilers.opt.dfsolver.DF_Solution;
018 import org.jikesrvm.compilers.opt.ir.BasicBlock;
019 import org.jikesrvm.compilers.opt.ir.BasicBlockEnumeration;
020 import org.jikesrvm.compilers.opt.ir.IR;
021
022 /**
023 * Calculate dominators for basic blocks.
024 * <p> Uses the algorithm contained in Dragon book, pg. 670-1.
025 * <pre>
026 * D(n0) := { n0 }
027 * for n in N - { n0 } do D(n) := N;
028 * while changes to any D(n) occur do
029 * for n in N - {n0} do
030 * D(n) := {n} U (intersect of D(p) over all predecessors p of n)
031 * </pre>
032 * <p> TODO: we do not support IRs with exception handlers!!
033 */
034 public class Dominators {
035 /**
036 * Control for debug output
037 */
038 static final boolean DEBUG = false;
039 /**
040 * Should we compute post-dominators instead of dominators? This is
041 * false by default.
042 */
043 static boolean COMPUTE_POST_DOMINATORS = false;
044
045 /**
046 * Calculate the dominators for an IR.
047 * <p> After this pass, each basic block's scrach field points to
048 * an <code> DominatorInfo </code> object, which holds the dominators
049 * of the basic block.
050 *
051 * @param ir the IR in question
052 */
053 public static void perform(IR ir) {
054 if (ir.hasReachableExceptionHandlers()) {
055 throw new OperationNotImplementedException("IR with exception handlers");
056 }
057 DominatorSystem system = new DominatorSystem(ir);
058 if (DEBUG) {
059 System.out.print("Solving...");
060 }
061 if (DEBUG) {
062 System.out.println(system);
063 }
064 system.solve();
065 if (DEBUG) {
066 System.out.println("done");
067 }
068 DF_Solution solution = system.getSolution();
069 if (DEBUG) {
070 System.out.println("Dominator Solution :" + solution);
071 }
072 if (DEBUG) {
073 System.out.print("Updating blocks ...");
074 }
075 updateBlocks(solution);
076 if (DEBUG) {
077 System.out.println("done.");
078 }
079 if (ir.options.PRINT_DOMINATORS) {
080 printDominators(ir);
081 }
082 }
083
084 /**
085 * Calculate the "approximate" dominators for an IR i.e., the
086 * dominators in the factored CFG rather than the normal CFG.
087 * <p> (No exception is thrown if the input IR has handler blocks.)
088 *
089 * <p> After this pass, each basic block's scratch field points to
090 * an DominatorInfo object, which holds the dominators
091 * of the basic block.
092 *
093 * @param ir the IR in question
094 */
095 public static void computeApproxDominators(IR ir) {
096 DominatorSystem system = new DominatorSystem(ir);
097 if (DEBUG) {
098 System.out.print("Solving...");
099 }
100 if (DEBUG) {
101 System.out.println(system);
102 }
103 system.solve();
104 if (DEBUG) {
105 System.out.println("done");
106 }
107 DF_Solution solution = system.getSolution();
108 if (DEBUG) {
109 System.out.println("Dominator Solution :" + solution);
110 }
111 if (DEBUG) {
112 System.out.print("Updating blocks ...");
113 }
114 updateBlocks(solution);
115 if (DEBUG) {
116 System.out.println("done.");
117 }
118 if (ir.options.PRINT_DOMINATORS) {
119 printDominators(ir);
120 }
121 }
122
123 /**
124 * Calculate the postdominators for an IR.
125 * <p> After this pass, each basic block's scrach field points to
126 * an DominatorInfo object, which holds the postdominators
127 * of the basic block.
128 *
129 * @param ir the IR in question
130 */
131 public static void computeApproxPostdominators(IR ir) {
132 Dominators.COMPUTE_POST_DOMINATORS = true;
133 DominatorSystem system = new DominatorSystem(ir);
134 if (DEBUG) {
135 System.out.print("Solving...");
136 }
137 if (DEBUG) {
138 System.out.println(system);
139 }
140 system.solve();
141 if (DEBUG) {
142 System.out.println("done");
143 }
144 DF_Solution solution = system.getSolution();
145 if (DEBUG) {
146 System.out.println("Postdominator Solution :" + solution);
147 }
148 if (DEBUG) {
149 System.out.print("Updating blocks ...");
150 }
151 updateBlocks(solution);
152 if (DEBUG) {
153 System.out.println("done.");
154 }
155 if (ir.options.PRINT_DOMINATORS) {
156 printDominators(ir);
157 }
158 Dominators.COMPUTE_POST_DOMINATORS = false;
159 }
160
161 /**
162 * For each basic block in the data flow system solution,
163 * create an <code> DominatorInfo </code> and store it in the basic
164 * blocks scratchObject
165 *
166 * @param solution the solution to the Dominators equations
167 */
168 public static void updateBlocks(DF_Solution solution) {
169 for (final DF_LatticeCell latticeCell : solution.values()) {
170 DominatorCell cell = (DominatorCell) latticeCell;
171 BasicBlock b = cell.block;
172 b.scratchObject = new DominatorInfo(cell.dominators);
173 if (DEBUG) {
174 System.out.println("Dominators of " + b + ":" + cell.dominators);
175 }
176 }
177 }
178
179 /**
180 * Print the (already calculated) dominators.
181 * @param ir the IR
182 */
183 public static void printDominators(IR ir) {
184 for (BasicBlockEnumeration e = ir.getBasicBlocks(); e.hasMoreElements();) {
185 BasicBlock b = e.next();
186 DominatorInfo i = (DominatorInfo) b.scratchObject;
187 System.out.println("Dominators of " + b + ":" + i.dominators);
188 }
189 }
190 }