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.bcp;
021:
022: import java.util.BitSet;
023: import java.util.IdentityHashMap;
024: import java.util.Iterator;
025: import java.util.LinkedList;
026:
027: import org.apache.bcel.classfile.Method;
028: import org.apache.bcel.generic.ConstantPoolGen;
029: import org.apache.bcel.generic.InstructionHandle;
030:
031: import edu.umd.cs.findbugs.SystemProperties;
032: import edu.umd.cs.findbugs.annotations.Nullable;
033: import edu.umd.cs.findbugs.ba.BasicBlock;
034: import edu.umd.cs.findbugs.ba.CFG;
035: import edu.umd.cs.findbugs.ba.CFGBuilderException;
036: import edu.umd.cs.findbugs.ba.ClassContext;
037: import edu.umd.cs.findbugs.ba.DFSEdgeTypes;
038: import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
039: import edu.umd.cs.findbugs.ba.DepthFirstSearch;
040: import edu.umd.cs.findbugs.ba.DominatorsAnalysis;
041: import edu.umd.cs.findbugs.ba.Edge;
042: import edu.umd.cs.findbugs.ba.Location;
043: import edu.umd.cs.findbugs.ba.vna.ValueNumberDataflow;
044: import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
045:
046: /**
047: * Match a ByteCodePattern against the code of a method, represented
048: * by a CFG. Produces some number of ByteCodePatternMatch objects, which
049: * indicate how the pattern matched the bytecode instructions in the method.
050: * <p/>
051: * <p> This code is a hack and should probably be rewritten.
052: *
053: * @author David Hovemeyer
054: * @see ByteCodePattern
055: */
056: public class PatternMatcher implements DFSEdgeTypes {
057: private static final boolean DEBUG = SystemProperties
058: .getBoolean("bcp.debug");
059: private static final boolean SHOW_WILD = SystemProperties
060: .getBoolean("bcp.showWild");
061:
062: private ByteCodePattern pattern;
063: private CFG cfg;
064: private ConstantPoolGen cpg;
065: private DepthFirstSearch dfs;
066: private ValueNumberDataflow vnaDataflow;
067: private DominatorsAnalysis domAnalysis;
068: private LinkedList<BasicBlock> workList;
069: private IdentityHashMap<BasicBlock, BasicBlock> visitedBlockMap;
070: private LinkedList<ByteCodePatternMatch> resultList;
071:
072: /**
073: * Constructor.
074: *
075: * @param pattern the ByteCodePattern to look for examples of
076: * @param classContext ClassContext for the class to analyze
077: * @param method the Method to analyze
078: */
079: public PatternMatcher(ByteCodePattern pattern,
080: ClassContext classContext, Method method)
081: throws CFGBuilderException, DataflowAnalysisException {
082: this .pattern = pattern;
083: this .cfg = classContext.getCFG(method);
084: this .cpg = classContext.getConstantPoolGen();
085: this .dfs = classContext.getDepthFirstSearch(method);
086: this .vnaDataflow = classContext.getValueNumberDataflow(method);
087: this .domAnalysis = classContext
088: .getNonExceptionDominatorsAnalysis(method);
089: this .workList = new LinkedList<BasicBlock>();
090: this .visitedBlockMap = new IdentityHashMap<BasicBlock, BasicBlock>();
091: this .resultList = new LinkedList<ByteCodePatternMatch>();
092: }
093:
094: /**
095: * Search for examples of the ByteCodePattern.
096: *
097: * @return this object
098: * @throws DataflowAnalysisException if the ValueNumberAnalysis did not produce useful
099: * values for the method
100: */
101: public PatternMatcher execute() throws DataflowAnalysisException {
102: workList.addLast(cfg.getEntry());
103:
104: while (!workList.isEmpty()) {
105: BasicBlock basicBlock = workList.removeLast();
106: visitedBlockMap.put(basicBlock, basicBlock);
107:
108: // Scan instructions of basic block for possible matches
109: BasicBlock.InstructionIterator i = basicBlock
110: .instructionIterator();
111: while (i.hasNext()) {
112: attemptMatch(basicBlock, i.duplicate());
113: i.next();
114: }
115:
116: // Add successors of the basic block (which haven't been visited already)
117: Iterator<BasicBlock> succIterator = cfg
118: .successorIterator(basicBlock);
119: while (succIterator.hasNext()) {
120: BasicBlock succ = succIterator.next();
121: if (visitedBlockMap.get(succ) == null)
122: workList.addLast(succ);
123: }
124: }
125:
126: return this ;
127: }
128:
129: /**
130: * Return an Iterator over the ByteCodePatternMatch objects representing
131: * successful matches of the ByteCodePattern.
132: */
133: public Iterator<ByteCodePatternMatch> byteCodePatternMatchIterator() {
134: return resultList.iterator();
135: }
136:
137: /**
138: * Attempt to begin a match.
139: *
140: * @param basicBlock the basic block
141: * @param instructionIterator the instruction iterator positioned just before
142: * the first instruction to be matched
143: */
144: private void attemptMatch(BasicBlock basicBlock,
145: BasicBlock.InstructionIterator instructionIterator)
146: throws DataflowAnalysisException {
147: work(new State(basicBlock, instructionIterator, pattern
148: .getFirst()));
149: }
150:
151: // For debugging - number the paths through the CFG
152: private int nextPath = 0;
153:
154: /**
155: * Object representing the current state of the
156: * matching algorithm. Provides convenient methods to
157: * implement the various steps of the algorithm.
158: */
159: private class State {
160: private BasicBlock basicBlock;
161: private BasicBlock.InstructionIterator instructionIterator;
162: private PatternElement patternElement;
163: private int matchCount;
164: private PatternElementMatch currentMatch;
165: private BindingSet bindingSet;
166: private boolean canFork;
167: private final int parentPath;
168: private final int path;
169:
170: /**
171: * Constructor.
172: * Builds the start state.
173: *
174: * @param basicBlock the initial basic block
175: * @param instructionIterator the instructionIterator indicating where
176: * to start matching
177: * @param patternElement the first PatternElement of the pattern
178: */
179: public State(BasicBlock basicBlock,
180: BasicBlock.InstructionIterator instructionIterator,
181: PatternElement patternElement) {
182: this (null, basicBlock, instructionIterator, patternElement,
183: 0, null, null, true);
184: }
185:
186: /**
187: * Constructor.
188: */
189: public State(@Nullable
190: State parent, BasicBlock basicBlock,
191: BasicBlock.InstructionIterator instructionIterator,
192: PatternElement patternElement, int matchCount,
193: @Nullable
194: PatternElementMatch currentMatch, @Nullable
195: BindingSet bindingSet, boolean canFork) {
196: this .basicBlock = basicBlock;
197: this .instructionIterator = instructionIterator;
198: this .patternElement = patternElement;
199: this .matchCount = matchCount;
200: this .currentMatch = currentMatch;
201: this .bindingSet = bindingSet;
202: this .canFork = canFork;
203: this .parentPath = (parent != null) ? parent.path : -1;
204: this .path = nextPath++;
205: }
206:
207: /**
208: * Make an exact copy of this object.
209: */
210: public State duplicate() {
211: return new State(this , basicBlock, instructionIterator,
212: patternElement, matchCount, currentMatch,
213: bindingSet, canFork);
214: }
215:
216: /**
217: * Get basic block.
218: */
219: public BasicBlock getBasicBlock() {
220: return basicBlock;
221: }
222:
223: /**
224: * Get current pattern element.
225: */
226: public PatternElement getPatternElement() {
227: return patternElement;
228: }
229:
230: /**
231: * Get current pattern element match.
232: */
233: public PatternElementMatch getCurrentMatch() {
234: return currentMatch;
235: }
236:
237: /**
238: * Determine if the match is complete.
239: */
240: public boolean isComplete() {
241: // We're done when we reach the end of the chain
242: // of pattern elements.
243: return patternElement == null;
244: }
245:
246: /**
247: * Get a ByteCodePatternMatch representing the complete match.
248: */
249: public ByteCodePatternMatch getResult() {
250: if (!isComplete())
251: throw new IllegalStateException("match not complete!");
252: return new ByteCodePatternMatch(bindingSet, currentMatch);
253: }
254:
255: /**
256: * Try to produce a new state that will finish matching
257: * the current element and start matching the next element.
258: * Returns null if the current element is not complete.
259: */
260: public State advanceToNextElement() {
261: if (!canFork || matchCount < patternElement.minOccur())
262: // Current element is not complete, or we already
263: // forked at this point
264: return null;
265:
266: // Create state to advance to matching next pattern element
267: // at current basic block and instruction.
268: State advance = new State(this , basicBlock,
269: instructionIterator.duplicate(), patternElement
270: .getNext(), 0, currentMatch, bindingSet,
271: true);
272:
273: // Now that this state has forked from this element
274: // at this instruction, it must not do so again.
275: this .canFork = false;
276:
277: return advance;
278: }
279:
280: /**
281: * Determine if the current pattern element can continue
282: * to match instructions.
283: */
284: public boolean currentElementCanContinue() {
285: return matchCount < patternElement.maxOccur();
286: }
287:
288: /**
289: * Determine if there are more instructions in the same basic block.
290: */
291: public boolean moreInstructionsInBasicBlock() {
292: return instructionIterator.hasNext();
293: }
294:
295: /**
296: * Match current pattern element with next instruction
297: * in basic block. Returns MatchResult if match succeeds,
298: * null otherwise.
299: */
300: public MatchResult matchNextInBasicBlock()
301: throws DataflowAnalysisException {
302: if (!moreInstructionsInBasicBlock())
303: throw new IllegalStateException("At end of BB!");
304:
305: // Move to location of next instruction to be matched
306: Location location = new Location(
307: instructionIterator.next(), basicBlock);
308: return matchLocation(location);
309: }
310:
311: /**
312: * Determine if it is possible to continue matching
313: * in a successor basic block.
314: */
315: public boolean canAdvanceToNextBasicBlock() {
316: return currentMatch == null
317: || currentMatch.allowTrailingEdges();
318: }
319:
320: /**
321: * Get most recently matched instruction.
322: */
323: public InstructionHandle getLastMatchedInstruction() {
324: if (currentMatch == null)
325: throw new IllegalStateException("no current match!");
326: return currentMatch
327: .getMatchedInstructionInstructionHandle();
328: }
329:
330: /**
331: * Return a new State for continuing the overall pattern match
332: * in a successor basic block.
333: *
334: * @param edge the Edge leading to the successor basic block
335: * @param matchResult a MatchResult representing the match of the
336: * last instruction in the predecessor block; null if none
337: */
338: public State advanceToSuccessor(Edge edge,
339: MatchResult matchResult) {
340: // If we have just matched an instruction, then we allow the
341: // matching PatternElement to choose which edges are acceptable.
342: // This allows PatternElements to select particular control edges;
343: // for example, only continue the pattern on the true branch
344: // of an "if" comparison.
345: if (matchResult != null
346: && !matchResult.getPatternElement().acceptBranch(
347: edge, getLastMatchedInstruction()))
348: return null;
349:
350: return new State(this , edge.getTarget(), edge.getTarget()
351: .instructionIterator(), patternElement, matchCount,
352: currentMatch, bindingSet, canFork);
353: }
354:
355: /**
356: * Determine if we need to look for a dominated instruction at
357: * this point in the search.
358: */
359: public boolean lookForDominatedInstruction() {
360: return patternElement.getDominatedBy() != null
361: && matchCount == 0;
362: }
363:
364: /**
365: * Return Iterator over states representing dominated instructions
366: * that continue the match.
367: */
368: public Iterator<State> dominatedInstructionStateIterator()
369: throws DataflowAnalysisException {
370: if (!lookForDominatedInstruction())
371: throw new IllegalStateException();
372: LinkedList<State> stateList = new LinkedList<State>();
373:
374: State dup = this .duplicate();
375:
376: if (currentMatch != null) {
377: // Find the referenced instruction.
378: PatternElementMatch dominator = currentMatch
379: .getFirstLabeledMatch(patternElement
380: .getDominatedBy());
381: BasicBlock domBlock = dominator.getBasicBlock();
382:
383: // Find all basic blocks dominated by the dominator block.
384: for (Iterator<BasicBlock> i = cfg.blockIterator(); i
385: .hasNext();) {
386: BasicBlock block = i.next();
387: if (block == domBlock)
388: continue;
389:
390: BitSet dominators = domAnalysis
391: .getResultFact(block);
392: if (dominators.get(domBlock.getLabel())) {
393: // This block is dominated by the dominator block.
394: // Each instruction in the block which matches the current pattern
395: // element is a new state continuing the match.
396: for (Iterator<InstructionHandle> j = block
397: .instructionIterator(); j.hasNext();) {
398: MatchResult matchResult = dup
399: .matchLocation(new Location(j
400: .next(), block));
401: if (matchResult != null) {
402: stateList.add(dup);
403: dup = this .duplicate();
404: }
405: }
406: }
407: }
408: }
409:
410: return stateList.iterator();
411: }
412:
413: private MatchResult matchLocation(Location location)
414: throws DataflowAnalysisException {
415: // Get the ValueNumberFrames before and after the instruction
416: ValueNumberFrame before = vnaDataflow
417: .getFactAtLocation(location);
418: ValueNumberFrame after = vnaDataflow
419: .getFactAfterLocation(location);
420:
421: // Try to match the instruction against the pattern element.
422: boolean debug = DEBUG
423: && (!(patternElement instanceof Wild) || SHOW_WILD);
424: if (debug) {
425: if (parentPath >= 0) {
426: System.out.print(parentPath + "->");
427: }
428: System.out.println(path
429: + ": Match "
430: + patternElement
431: + " against "
432: + location.getHandle()
433: + " "
434: + (bindingSet != null ? bindingSet.toString()
435: : "[]") + "...");
436: }
437: MatchResult matchResult = patternElement.match(location
438: .getHandle(), cpg, before, after, bindingSet);
439: if (debug)
440: System.out.println("\t"
441: + ((matchResult != null) ? " ==> MATCH"
442: : " ==> NOT A MATCH"));
443: if (matchResult != null) {
444: // Successful match!
445: // Update state to reflect that the match has occurred.
446: ++matchCount;
447: canFork = true;
448: currentMatch = new PatternElementMatch(matchResult
449: .getPatternElement(), location.getHandle(),
450: location.getBasicBlock(), matchCount,
451: currentMatch);
452: bindingSet = matchResult.getBindingSet();
453: }
454: return matchResult;
455: }
456: }
457:
458: /**
459: * Match a sequence of pattern elements, starting at the given one.
460: * The InstructionIterator should generally be positioned just before
461: * the next instruction to be matched. However, it may be positioned
462: * at the end of a basic block, in which case nothing will happen except
463: * that we will try to continue the match in the non-backedge successors
464: * of the basic block.
465: */
466: private void work(State state) throws DataflowAnalysisException {
467: // Have we reached the end of the pattern?
468: if (state.isComplete()) {
469: // This is a complete match.
470: if (DEBUG)
471: System.out.println("FINISHED A MATCH!");
472: resultList.add(state.getResult());
473: return;
474: }
475:
476: // If we've reached the minimum number of occurrences for this
477: // pattern element, we can advance to the next pattern element without trying
478: // to match this instruction again. We make sure that we only advance to
479: // the next element once for this matchCount.
480: State advance = state.advanceToNextElement();
481: if (advance != null) {
482: work(advance);
483: }
484:
485: // If we've reached the maximum number of occurrences for this
486: // pattern element, then we can't continue.
487: if (!state.currentElementCanContinue())
488: return;
489:
490: MatchResult matchResult = null;
491:
492: // Are we looking for an instruction dominated by an earlier
493: // matched instruction?
494: if (state.lookForDominatedInstruction()) {
495: for (Iterator<State> i = state
496: .dominatedInstructionStateIterator(); i.hasNext();)
497: work(i.next());
498: return;
499: }
500:
501: // Is there another instruction in this basic block?
502: if (state.moreInstructionsInBasicBlock()) {
503: // Try to match it.
504: matchResult = state.matchNextInBasicBlock();
505: if (matchResult == null)
506: return;
507: }
508:
509: // Continue the match at each successor instruction,
510: // using the same PatternElement.
511: if (state.moreInstructionsInBasicBlock()) {
512: // Easy case; continue matching in the same basic block.
513: work(state);
514: } else if (state.canAdvanceToNextBasicBlock()) {
515: // We've reached the end of the basic block.
516: // Try to advance to the successors of this basic block,
517: // ignoring loop backedges.
518: Iterator<Edge> i = cfg.outgoingEdgeIterator(state
519: .getBasicBlock());
520: BitSet visitedSuccessorSet = new BitSet();
521: while (i.hasNext()) {
522: Edge edge = i.next();
523: if (dfs.getDFSEdgeType(edge) == BACK_EDGE)
524: continue;
525:
526: BasicBlock destBlock = edge.getTarget();
527: int destId = destBlock.getLabel();
528:
529: // CFGs can have duplicate edges
530: if (visitedSuccessorSet.get(destId))
531: continue;
532: visitedSuccessorSet.set(destId, true);
533:
534: // See if we can continue matching in the successor basic block.
535: State succState = state.advanceToSuccessor(edge,
536: matchResult);
537: if (succState != null) {
538: work(succState);
539: }
540: }
541: }
542:
543: }
544: }
545:
546: // vim:ts=4
|