001: /*
002: * Bytecode Analysis Framework
003: * Copyright (C) 2003-2007 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 org.apache.bcel.generic.InstructionHandle;
023:
024: import edu.umd.cs.findbugs.annotations.CheckForNull;
025:
026: /**
027: * A dataflow analysis to be used with the {@link Dataflow} class.
028: *
029: * <p>
030: * In order to avoid duplicating
031: * functionality (such as caching of start and result facts),
032: * most analyses should extend the {@link BasicAbstractDataflowAnalysis}
033: * or {@link AbstractDataflowAnalysis} classes rather than
034: * directly implementing this interface.
035: * </p>
036: *
037: * @author David Hovemeyer
038: * @see Dataflow
039: */
040: public interface DataflowAnalysis<Fact> {
041: /**
042: * Create empty (uninitialized) dataflow facts for one program point.
043: * A valid value will be copied into it before it is used.
044: */
045: public Fact createFact();
046:
047: /**
048: * Get the start fact for given basic block.
049: *
050: * @param block the basic block
051: */
052: public Fact getStartFact(BasicBlock block);
053:
054: /**
055: * Get the result fact for given basic block.
056: *
057: * @param block the basic block
058: */
059: public Fact getResultFact(BasicBlock block);
060:
061: /**
062: * Get dataflow fact at (just before) given Location.
063: * Note "before" is meant in the logical sense, so for backward analyses,
064: * before means after the location in the control flow sense.
065: *
066: * @param location the Location
067: * @return the dataflow value at given Location
068: * @throws DataflowAnalysisException
069: */
070: public Fact getFactAtLocation(Location location)
071: throws DataflowAnalysisException;
072:
073: /**
074: * Get the dataflow fact representing the point just after given Location.
075: * Note "after" is meant in the logical sense, so for backward analyses,
076: * after means before the location in the control flow sense.
077: *
078: * @param location the Location
079: * @return the dataflow value after given Location
080: * @throws DataflowAnalysisException
081: */
082: public Fact getFactAfterLocation(Location location)
083: throws DataflowAnalysisException;
084:
085: /**
086: * Get the fact that is true on the given control edge.
087: *
088: * @param edge the edge
089: * @return the fact that is true on the edge
090: * @throws DataflowAnalysisException
091: */
092: public Fact getFactOnEdge(Edge edge)
093: throws DataflowAnalysisException;
094:
095: /**
096: * Copy dataflow facts.
097: */
098: public void copy(Fact source, Fact dest);
099:
100: /**
101: * Initialize the "entry" fact for the graph.
102: */
103: public void initEntryFact(Fact result)
104: throws DataflowAnalysisException;
105:
106: /**
107: * Make given fact the top value.
108: */
109: public void makeFactTop(Fact fact);
110:
111: /**
112: * Is the given fact the top value.
113: */
114: public boolean isTop(Fact fact);
115:
116: /**
117: * Returns true if the analysis is forwards, false if backwards.
118: */
119: public boolean isForwards();
120:
121: /**
122: * Return the BlockOrder specifying the order in which BasicBlocks
123: * should be visited in the main dataflow loop.
124: *
125: * @param cfg the CFG upon which we're performing dataflow analysis
126: */
127: public BlockOrder getBlockOrder(CFG cfg);
128:
129: /**
130: * Are given dataflow facts the same?
131: */
132: public boolean same(Fact fact1, Fact fact2);
133:
134: /**
135: * Transfer function for the analysis.
136: * Taking dataflow facts at start (which might be either the entry or
137: * exit of the block, depending on whether the analysis is forwards
138: * or backwards), modify result to be the facts at the other end
139: * of the block.
140: *
141: * @param basicBlock the basic block
142: * @param end if nonnull, stop before considering this instruction;
143: * otherwise, consider all of the instructions in the basic block
144: * @param start dataflow facts at beginning of block (if forward analysis)
145: * or end of block (if backwards analysis)
146: * @param result resulting dataflow facts at other end of block
147: */
148: public void transfer(BasicBlock basicBlock, @CheckForNull
149: InstructionHandle end, Fact start, Fact result)
150: throws DataflowAnalysisException;
151:
152: /**
153: * Edge transfer function.
154: * Modify the given fact that is true on the (logical) edge source
155: * to modify it so that it is true at the (logical) edge target.
156: *
157: * <p>
158: * A do-nothing implementation is legal, and appropriate for
159: * analyses where branches are not significant.
160: * </p>
161: *
162: * @param edge the Edge
163: * @param fact a dataflow fact
164: * @throws DataflowAnalysisException
165: */
166: public void edgeTransfer(Edge edge, Fact fact)
167: throws DataflowAnalysisException;
168:
169: /**
170: * Meet a dataflow fact associated with an incoming edge into another fact.
171: * This is used to determine the start fact for a basic block.
172: *
173: * @param fact the predecessor fact (incoming edge)
174: * @param edge the edge from the predecessor
175: * @param result the result fact
176: */
177: public void meetInto(Fact fact, Edge edge, Fact result)
178: throws DataflowAnalysisException;
179:
180: /**
181: * Called before beginning an iteration of analysis.
182: * Each iteration visits every basic block in the CFG.
183: */
184: public void startIteration();
185:
186: /**
187: * Called after finishing an iteration of analysis.
188: */
189: public void finishIteration();
190:
191: public int getLastUpdateTimestamp(Fact fact);
192:
193: public void setLastUpdateTimestamp(Fact fact, int timestamp);
194:
195: /**
196: * Return a String representation of given Fact.
197: * For debugging purposes.
198: *
199: * @param fact a dataflow fact
200: * @return String representation of the fact
201: */
202: public String factToString(Fact fact);
203: }
204:
205: // vim:ts=4
|