KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > edu > umd > cs > findbugs > ba > AbstractDominatorsAnalysis


1 /*
2  * Bytecode Analysis Framework
3  * Copyright (C) 2003,2004 University of Maryland
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  */

19
20 package edu.umd.cs.findbugs.ba;
21
22 import java.util.BitSet JavaDoc;
23 import java.util.IdentityHashMap JavaDoc;
24 import java.util.Iterator JavaDoc;
25 import java.util.Map JavaDoc;
26
27 import org.apache.bcel.generic.InstructionHandle;
28
29 import edu.umd.cs.findbugs.annotations.CheckForNull;
30
31 /**
32  * A dataflow analysis to compute dominator relationships between
33  * basic blocks. Use the {@link #getResultFact} method to get the dominator
34  * set for a given basic block. The dominator sets are represented using
35  * the {@link java.util.BitSet} class, with the individual bits
36  * corresponding to the IDs of basic blocks.
37  * <p/>
38  * <p> Subclasses extend this class to compute either dominators
39  * or postdominators.
40  * <p/>
41  * <p> An EdgeChooser may be specified to select which edges
42  * to take into account. For example, exception edges could be
43  * ignored.</p>
44  *
45  * @author David Hovemeyer
46  * @see DataflowAnalysis
47  * @see CFG
48  * @see BasicBlock
49  */

50 public abstract class AbstractDominatorsAnalysis extends BasicAbstractDataflowAnalysis<BitSet JavaDoc> {
51     private final CFG cfg;
52     private EdgeChooser edgeChooser;
53     
54     /**
55      * Constructor.
56      *
57      * @param cfg the CFG to compute dominator relationships for
58      * @param ignoreExceptionEdges true if exception edges should be ignored
59      */

60     public AbstractDominatorsAnalysis(CFG cfg, final boolean ignoreExceptionEdges) {
61         this(cfg, new EdgeChooser() {
62             public boolean choose(Edge edge) {
63                 if (ignoreExceptionEdges && edge.isExceptionEdge())
64                     return false;
65                 else
66                     return true;
67             }
68         });
69     }
70
71     /**
72      * Constructor.
73      *
74      * @param cfg the CFG to compute dominator relationships for
75      * @param edgeChooser EdgeChooser to choose which Edges to consider significant
76      */

77     public AbstractDominatorsAnalysis(CFG cfg, EdgeChooser edgeChooser) {
78         this.cfg = cfg;
79         this.edgeChooser = edgeChooser;
80     }
81
82     public BitSet JavaDoc createFact() {
83         return new BitSet JavaDoc();
84     }
85
86     public void copy(BitSet JavaDoc source, BitSet JavaDoc dest) {
87         dest.clear();
88         dest.or(source);
89     }
90
91     public void initEntryFact(BitSet JavaDoc result) {
92         // No blocks dominate the entry block
93
result.clear();
94     }
95
96     public void initResultFact(BitSet JavaDoc result) {
97         makeFactTop(result);
98     }
99
100     public boolean isTop(BitSet JavaDoc fact) {
101         // We represent TOP as a bitset with an illegal bit set
102
return fact.get(cfg.getNumBasicBlocks());
103     }
104
105     public void makeFactTop(BitSet JavaDoc fact) {
106         // We represent TOP as a bitset with an illegal bit set
107
fact.set(cfg.getNumBasicBlocks());
108     }
109
110     public boolean same(BitSet JavaDoc fact1, BitSet JavaDoc fact2) {
111         return fact1.equals(fact2);
112     }
113
114     public void transfer(BasicBlock basicBlock, @CheckForNull InstructionHandle end, BitSet JavaDoc start, BitSet JavaDoc result) throws DataflowAnalysisException {
115         // Start with intersection of dominators of predecessors
116
copy(start, result);
117
118         if (!isTop(result)) {
119             // Every block dominates itself
120
result.set(basicBlock.getId());
121         }
122     }
123
124     public void meetInto(BitSet JavaDoc fact, Edge edge, BitSet JavaDoc result) throws DataflowAnalysisException {
125         if (!edgeChooser.choose(edge))
126             return;
127
128         if (isTop(fact))
129             return;
130         else if (isTop(result))
131             copy(fact, result);
132         else
133         // Meet is intersection
134
result.and(fact);
135     }
136
137     /**
138      * Get a bitset containing the unique IDs of
139      * all blocks which dominate (or postdominate) the given block.
140      *
141      * @param block a BasicBlock
142      * @return BitSet of the unique IDs of all blocks that dominate
143      * (or postdominate) the BasicBlock
144      */

145     public BitSet JavaDoc getAllDominatorsOf(BasicBlock block) {
146         return getResultFact(block);
147     }
148
149     /**
150      * Get a bitset containing the unique IDs of
151      * all blocks in CFG dominated (or postdominated, depending
152      * on how the analysis was done) by given block.
153      *
154      * @param dominator we want to get all blocks dominated (or postdominated)
155      * by this block
156      * @return BitSet of the ids of all blocks dominated by the given block
157      */

158     public BitSet JavaDoc getAllDominatedBy(BasicBlock dominator) {
159         BitSet JavaDoc allDominated = new BitSet JavaDoc();
160         for (Iterator JavaDoc<BasicBlock> i = cfg.blockIterator(); i.hasNext();) {
161             BasicBlock block = i.next();
162             BitSet JavaDoc dominators = getResultFact(block);
163             if (dominators.get(dominator.getId()))
164                 allDominated.set(block.getId());
165         }
166         return allDominated;
167     }
168
169 }
170
171 // vim:ts=4
172
Popular Tags