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