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 java.util.Enumeration;
016
017 import org.jikesrvm.VM;
018 import org.jikesrvm.compilers.opt.dfsolver.DF_LatticeCell;
019 import org.jikesrvm.compilers.opt.dfsolver.DF_System;
020 import org.jikesrvm.compilers.opt.ir.BasicBlock;
021 import org.jikesrvm.compilers.opt.ir.IR;
022
023 /**
024 * Implementation of the dataflow equation system to calculate dominators.
025 */
026 class DominatorSystem extends DF_System {
027
028 /**
029 * The governing IR.
030 */
031 private final IR ir;
032
033 /**
034 * Default constructor.
035 * @param ir the governing IR
036 */
037 public DominatorSystem(IR ir) {
038 this.ir = ir;
039 setupEquations();
040 }
041
042 /**
043 * Go through each basic block in the IR, and add equations
044 * to the system as required.
045 * <p> Uses the algorithm contained in Dragon book, pg. 670-1.
046 * <pre>
047 * D(n0) := { n0 }
048 * for n in N - { n0 } do D(n) := N;
049 * while changes to any D(n) occur do
050 * for n in N - {n0} do
051 * D(n) := {n} U (intersect of D(p) over all predecessors p of n)
052 * </pre>
053 */
054 void setupEquations() {
055 // loop through each basic block in the IR
056 for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
057 BasicBlock bb = e.nextElement();
058 // add a data-flow equation for this basic block
059 // DOM(n) = {n} MEET {pred(n)}
060 DF_LatticeCell dom = findOrCreateCell(bb);
061 DF_LatticeCell[] pred = getCellsForPredecessors(bb);
062 newEquation(dom, DominatorOperator.MEET, pred);
063 }
064 }
065
066 /**
067 * Initialize the lattice variables (Dominator sets) for
068 * each basic block.
069 */
070 @Override
071 protected void initializeLatticeCells() {
072 if (Dominators.COMPUTE_POST_DOMINATORS) {
073 BasicBlock exit = ir.cfg.exit();
074 DominatorCell last = (DominatorCell) getCell(exit);
075 for (final DF_LatticeCell latticeCell : cells.values()) {
076 DominatorCell cell = (DominatorCell) latticeCell;
077 if (cell == last) {
078 cell.addSingleBlock(cell.block);
079 } else {
080 cell.setTOP(ir);
081 }
082 }
083 } else {
084 BasicBlock start = ir.cfg.entry();
085 DominatorCell first = (DominatorCell) getCell(start);
086 for (final DF_LatticeCell latticeCell : cells.values()) {
087 DominatorCell cell = (DominatorCell) latticeCell;
088 if (cell == first) {
089 cell.addSingleBlock(cell.block);
090 } else {
091 cell.setTOP(ir);
092 }
093 }
094 }
095 }
096
097 /**
098 * Initialize the work list for the dataflow equation system.
099 * <p> The initial work list is every equation containing the start
100 * node.
101 */
102 @Override
103 protected void initializeWorkList() {
104 if (Dominators.COMPUTE_POST_DOMINATORS) {
105 // Add every equation to work list (to be safe)
106 // WARNING: an "end node" may be part of a cycle
107 for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
108 BasicBlock bb = e.nextElement();
109 addCellAppearancesToWorkList(getCell(bb));
110 }
111 } else {
112 DominatorCell first = (DominatorCell) getCell(ir.cfg.entry());
113 addCellAppearancesToWorkList(first);
114 }
115 }
116
117 /**
118 * Get the DF_LatticeCell key corresponding to a basic block
119 * @param bb the basic block
120 * @return the key (just the block itself)
121 */
122 Object getKey(BasicBlock bb) {
123 return bb;
124 }
125
126 /**
127 * Make a new DF_LatticeCell key corresponding to a basic block
128 * @param key the basic block
129 * @return the new cell
130 */
131 @Override
132 protected DF_LatticeCell makeCell(Object key) {
133 return new DominatorCell((BasicBlock) key, ir);
134 }
135
136 /**
137 * Return a list of lattice cells corresponding to the
138 * predecessors of a basic block.
139 * @param bb the basic block
140 */
141 DF_LatticeCell[] getCellsForPredecessors(BasicBlock bb) {
142 if (Dominators.COMPUTE_POST_DOMINATORS) {
143 /****
144 if ( bb.mayThrowUncaughtException() ) {
145 if (Dominators.DEBUG) VM.sysWrite("LOCATION #1 ...\n");
146 // Include exit node as an output node
147 DF_LatticeCell s[] = new DF_LatticeCell[bb.getNumberOfOut()+1];
148 Enumeration<BasicBlock> e = bb.getOut();
149 for (int i=0; i<s.length-1; i++ ) {
150 BasicBlock p = e.next();
151 s[i] = findOrCreateCell(getKey(p));
152 }
153 s[s.length-1] = findOrCreateCell(getKey(ir.cfg.exit()));
154 return s;
155 }
156 else
157 ****/
158 {
159 if (Dominators.DEBUG) {
160 VM.sysWrite("LOCATION #2 ...\n");
161 }
162 DF_LatticeCell[] s = new DF_LatticeCell[bb.getNumberOfOut()];
163 Enumeration<BasicBlock> e = bb.getOut();
164 for (int i = 0; i < s.length; i++) {
165 BasicBlock p = e.nextElement();
166 s[i] = findOrCreateCell(getKey(p));
167 }
168 return s;
169 }
170 } else {
171 if (Dominators.DEBUG) {
172 System.out.println("LOCATION #3 ...");
173 }
174 DF_LatticeCell[] s = new DF_LatticeCell[bb.getNumberOfIn()];
175 Enumeration<BasicBlock> e = bb.getIn();
176 for (int i = 0; i < s.length; i++) {
177 BasicBlock p = e.nextElement();
178 s[i] = findOrCreateCell(getKey(p));
179 }
180 return s;
181 }
182 }
183 }