001: /*
002: * Bytecode Analysis Framework
003: * Copyright (C) 2003,2004 University of Maryland
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019:
020: package edu.umd.cs.findbugs.ba;
021:
022: import java.util.BitSet;
023: import java.util.Iterator;
024:
025: import org.apache.bcel.generic.InstructionHandle;
026:
027: import edu.umd.cs.findbugs.annotations.CheckForNull;
028:
029: /**
030: * A dataflow analysis to compute dominator relationships between
031: * basic blocks. Use the {@link #getResultFact} method to get the dominator
032: * set for a given basic block. The dominator sets are represented using
033: * the {@link java.util.BitSet} class, with the individual bits
034: * corresponding to the IDs of basic blocks.
035: * <p/>
036: * <p> Subclasses extend this class to compute either dominators
037: * or postdominators.
038: * <p/>
039: * <p> An EdgeChooser may be specified to select which edges
040: * to take into account. For example, exception edges could be
041: * ignored.</p>
042: *
043: * @author David Hovemeyer
044: * @see DataflowAnalysis
045: * @see CFG
046: * @see BasicBlock
047: */
048: public abstract class AbstractDominatorsAnalysis extends
049: BasicAbstractDataflowAnalysis<BitSet> {
050: private final CFG cfg;
051: private EdgeChooser edgeChooser;
052:
053: /**
054: * Constructor.
055: *
056: * @param cfg the CFG to compute dominator relationships for
057: * @param ignoreExceptionEdges true if exception edges should be ignored
058: */
059: public AbstractDominatorsAnalysis(CFG cfg,
060: final boolean ignoreExceptionEdges) {
061: this (cfg, new EdgeChooser() {
062: public boolean choose(Edge edge) {
063: if (ignoreExceptionEdges && edge.isExceptionEdge())
064: return false;
065: else
066: return true;
067: }
068: });
069: }
070:
071: /**
072: * Constructor.
073: *
074: * @param cfg the CFG to compute dominator relationships for
075: * @param edgeChooser EdgeChooser to choose which Edges to consider significant
076: */
077: public AbstractDominatorsAnalysis(CFG cfg, EdgeChooser edgeChooser) {
078: this .cfg = cfg;
079: this .edgeChooser = edgeChooser;
080: }
081:
082: public BitSet createFact() {
083: return new BitSet();
084: }
085:
086: public void copy(BitSet source, BitSet dest) {
087: dest.clear();
088: dest.or(source);
089: }
090:
091: public void initEntryFact(BitSet result) {
092: // No blocks dominate the entry block
093: result.clear();
094: }
095:
096: public boolean isTop(BitSet fact) {
097: // We represent TOP as a bitset with an illegal bit set
098: return fact.get(cfg.getNumBasicBlocks());
099: }
100:
101: public void makeFactTop(BitSet fact) {
102: // We represent TOP as a bitset with an illegal bit set
103: fact.set(cfg.getNumBasicBlocks());
104: }
105:
106: public boolean same(BitSet fact1, BitSet fact2) {
107: return fact1.equals(fact2);
108: }
109:
110: public void transfer(BasicBlock basicBlock, @CheckForNull
111: InstructionHandle end, BitSet start, BitSet result)
112: throws DataflowAnalysisException {
113: // Start with intersection of dominators of predecessors
114: copy(start, result);
115:
116: if (!isTop(result)) {
117: // Every block dominates itself
118: result.set(basicBlock.getLabel());
119: }
120: }
121:
122: public void meetInto(BitSet fact, Edge edge, BitSet result)
123: throws DataflowAnalysisException {
124: if (!edgeChooser.choose(edge))
125: return;
126:
127: if (isTop(fact))
128: return;
129: else if (isTop(result))
130: copy(fact, result);
131: else
132: // Meet is intersection
133: result.and(fact);
134: }
135:
136: /**
137: * Get a bitset containing the unique IDs of
138: * all blocks which dominate (or postdominate) the given block.
139: *
140: * @param block a BasicBlock
141: * @return BitSet of the unique IDs of all blocks that dominate
142: * (or postdominate) the BasicBlock
143: */
144: public BitSet getAllDominatorsOf(BasicBlock block) {
145: return getResultFact(block);
146: }
147:
148: /**
149: * Get a bitset containing the unique IDs of
150: * all blocks in CFG dominated (or postdominated, depending
151: * on how the analysis was done) by given block.
152: *
153: * @param dominator we want to get all blocks dominated (or postdominated)
154: * by this block
155: * @return BitSet of the ids of all blocks dominated by the given block
156: */
157: public BitSet getAllDominatedBy(BasicBlock dominator) {
158: BitSet allDominated = new BitSet();
159: for (Iterator<BasicBlock> i = cfg.blockIterator(); i.hasNext();) {
160: BasicBlock block = i.next();
161: BitSet dominators = getResultFact(block);
162: if (dominators.get(dominator.getLabel()))
163: allDominated.set(block.getLabel());
164: }
165: return allDominated;
166: }
167:
168: }
169:
170: // vim:ts=4
|