001: /*
002: * Bytecode Analysis Framework
003: * Copyright (C) 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:
024: import org.apache.bcel.classfile.Method;
025: import org.apache.bcel.generic.IINC;
026: import org.apache.bcel.generic.IndexedInstruction;
027: import org.apache.bcel.generic.Instruction;
028: import org.apache.bcel.generic.InstructionHandle;
029: import org.apache.bcel.generic.LoadInstruction;
030: import org.apache.bcel.generic.LocalVariableInstruction;
031: import org.apache.bcel.generic.MethodGen;
032: import org.apache.bcel.generic.RET;
033: import org.apache.bcel.generic.StoreInstruction;
034:
035: /**
036: * Dataflow analysis to find live stores of locals.
037: * This is just a backward analysis to see which loads
038: * reach stores of the same local.
039: *
040: * <p> This analysis also computes which stores that were
041: * killed by a subsequent store on any subsequent reachable path.
042: * (The FindDeadLocalStores detector uses this information
043: * to reduce false positives.)
044: *
045: * @author David Hovemeyer
046: */
047: public class LiveLocalStoreAnalysis extends
048: BackwardDataflowAnalysis<BitSet> implements Debug {
049: private int topBit;
050: private int killedByStoreOffset;
051:
052: public LiveLocalStoreAnalysis(MethodGen methodGen,
053: ReverseDepthFirstSearch rdfs, DepthFirstSearch dfs) {
054: super (rdfs, dfs);
055: this .topBit = methodGen.getMaxLocals() * 2;
056: this .killedByStoreOffset = methodGen.getMaxLocals();
057: }
058:
059: public BitSet createFact() {
060: return new BitSet();
061: }
062:
063: public void copy(BitSet source, BitSet dest) {
064: dest.clear();
065: dest.or(source);
066: }
067:
068: public void initEntryFact(BitSet result)
069: throws DataflowAnalysisException {
070: result.clear();
071: }
072:
073: public void makeFactTop(BitSet fact) {
074: fact.clear();
075: fact.set(topBit);
076: }
077:
078: public boolean same(BitSet fact1, BitSet fact2) {
079: return fact1.equals(fact2);
080: }
081:
082: public void meetInto(BitSet fact, Edge edge, BitSet result)
083: throws DataflowAnalysisException {
084: verifyFact(fact);
085: verifyFact(result);
086:
087: if (isTop(fact)) {
088: // Nothing to do, result stays the same
089: } else if (isTop(result)) {
090: // Result is top, so it takes the value of fact
091: copy(fact, result);
092: } else {
093: // Meet is union
094: result.or(fact);
095: }
096:
097: verifyFact(result);
098: }
099:
100: @Override
101: public void transferInstruction(InstructionHandle handle,
102: BasicBlock basicBlock, BitSet fact)
103: throws DataflowAnalysisException {
104: if (!isFactValid(fact))
105: return;
106:
107: Instruction ins = handle.getInstruction();
108:
109: if (ins instanceof StoreInstruction) {
110: // Local is stored: any live stores on paths leading
111: // to this instruction are now dead
112:
113: LocalVariableInstruction store = (LocalVariableInstruction) ins;
114: int local = store.getIndex();
115: fact.clear(local);
116: fact.set(local + killedByStoreOffset);
117: }
118:
119: if (ins instanceof LoadInstruction || ins instanceof IINC
120: || ins instanceof RET) {
121: // Local is loaded: it will be live on any path leading
122: // to this instruction
123:
124: IndexedInstruction load = (IndexedInstruction) ins;
125: int local = load.getIndex();
126: fact.set(local);
127: fact.clear(local + killedByStoreOffset);
128: }
129:
130: if (!isFactValid(fact))
131: throw new IllegalStateException("Fact become invalid");
132: }
133:
134: @Override
135: public boolean isFactValid(BitSet fact) {
136: verifyFact(fact);
137: return !isTop(fact);
138: }
139:
140: /**
141: * @param fact
142: */
143: private void verifyFact(BitSet fact) {
144: if (VERIFY_INTEGRITY) {
145: if (isTop(fact) && fact.nextSetBit(0) < topBit)
146: throw new IllegalStateException();
147: }
148: }
149:
150: @Override
151: public String factToString(BitSet fact) {
152: if (isTop(fact))
153: return "[TOP]";
154: StringBuilder buf = new StringBuilder("[ ");
155: boolean empty = true;
156: for (int i = 0; i < killedByStoreOffset; i++) {
157: boolean killedByStore = killedByStore(fact, i);
158: boolean storeAlive = isStoreAlive(fact, i);
159: if (!storeAlive && !killedByStore)
160: continue;
161: if (!empty)
162: buf.append(", ");
163: empty = false;
164: buf.append(i);
165: if (storeAlive)
166: buf.append("L");
167: if (killedByStore)
168: buf.append("k");
169: }
170: buf.append("]");
171: return buf.toString();
172: }
173:
174: /**
175: * Return whether or not given fact is the special TOP value.
176: */
177: public boolean isTop(BitSet fact) {
178: return fact.get(topBit);
179: }
180:
181: /**
182: * Return whether or not a store of given local is alive.
183: *
184: * @param fact a dataflow fact created by this analysis
185: * @param local the local
186: */
187: public boolean isStoreAlive(BitSet fact, int local) {
188: return fact.get(local);
189: }
190:
191: /**
192: * Return whether or not a store of given local was killed
193: * by a subsequent (dominated) store.
194: */
195: public boolean killedByStore(BitSet fact, int local) {
196: return fact.get(local + killedByStoreOffset);
197: }
198:
199: public static void main(String[] argv) throws Exception {
200: if (argv.length != 1) {
201: System.err.println("Usage: "
202: + LiveLocalStoreAnalysis.class.getName()
203: + " <classfile>");
204: System.exit(1);
205: }
206:
207: String filename = argv[0];
208:
209: DataflowTestDriver<BitSet, LiveLocalStoreAnalysis> driver = new DataflowTestDriver<BitSet, LiveLocalStoreAnalysis>() {
210:
211: @Override
212: public Dataflow<BitSet, LiveLocalStoreAnalysis> createDataflow(
213: ClassContext classContext, Method method)
214: throws CFGBuilderException,
215: DataflowAnalysisException {
216: return classContext.getLiveLocalStoreDataflow(method);
217: }
218: };
219:
220: driver.execute(filename);
221: }
222: }
223:
224: // vim:ts=4
|