org.apache.bcel.util

Class InstructionFinder


public class InstructionFinder
extends java.lang.Object

InstructionFinder is a tool to search for given instructions patterns, i.e., match sequences of instructions in an instruction list via regular expressions. This can be used, e.g., in order to implement a peep hole optimizer that looks for code patterns and replaces them with faster equivalents.

This class internally uses the Regexp package to search for regular expressions. A typical application would look like this:

 
  
   InstructionFinder f   = new InstructionFinder(il);
   String            pat = "IfInstruction ICONST_0 GOTO ICONST_1 NOP (IFEQ|IFNE)";
   
   for(Iterator i = f.search(pat, constraint); i.hasNext(); ) {
   InstructionHandle[] match = (InstructionHandle[])i.next();
   ...
   il.delete(match[1], match[5]);
   ...
   }
   
  
 
Version:
$Id: InstructionFinder.java 386056 2006-03-15 11:31:56Z tcurdt $
Author:
M. Dahm
See Also:
Instruction, InstructionList

Nested Class Summary

static interface
InstructionFinder.CodeConstraint
Code patterns found may be checked using an additional user-defined constraint object whether they really match the needed criterion.

Field Summary

private static int
NO_OPCODES
private static int
OFFSET
private InstructionHandle[]
handles
private InstructionList
il
private String
il_string
private static Map
map

Constructor Summary

InstructionFinder(InstructionList il)

Method Summary

private static String
compilePattern(String pattern)
Replace symbolic names of instructions with the appropiate character and remove all white space from string.
InstructionList
getInstructionList()
private InstructionHandle[]
getMatch(int matched_from, int match_length)
private static char
makeChar(short opcode)
Convert opcode number to char.
private static String
mapName(String pattern)
Map symbolic instruction names like "getfield" to a single character.
private static String
pattern2string(String pattern)
private static String
pattern2string(String pattern, boolean make_string)
private static String
precompile(short from, short to, short extra)
void
reread()
Reread the instruction list, e.g., after you've altered the list upon a match.
Iterator
search(String pattern)
Start search beginning from the start of the given instruction list.
Iterator
search(String pattern, InstructionHandle from)
Start search beginning from `from'.
Iterator
search(String pattern, InstructionHandle from, InstructionFinder.CodeConstraint constraint)
Search for the given pattern in the instruction list.
Iterator
search(String pattern, InstructionFinder.CodeConstraint constraint)
Start search beginning from the start of the given instruction list.

Field Details

NO_OPCODES

private static final int NO_OPCODES
Field Value:
256

OFFSET

private static final int OFFSET
Field Value:
32767

handles

private InstructionHandle[] handles

il

private InstructionList il

il_string

private String il_string

map

private static final Map map

Constructor Details

InstructionFinder

public InstructionFinder(InstructionList il)
Parameters:
il - instruction list to search for given patterns

Method Details

compilePattern

private static final String compilePattern(String pattern)
Replace symbolic names of instructions with the appropiate character and remove all white space from string. Meta characters such as +, * are ignored.
Parameters:
pattern - The pattern to compile
Returns:
translated regular expression string

getInstructionList

public final InstructionList getInstructionList()
Returns:
the inquired instruction list

getMatch

private InstructionHandle[] getMatch(int matched_from,
                                     int match_length)
Returns:
the matched piece of code as an array of instruction (handles)

makeChar

private static final char makeChar(short opcode)
Convert opcode number to char.

mapName

private static final String mapName(String pattern)
Map symbolic instruction names like "getfield" to a single character.
Parameters:
pattern - instruction pattern in lower case
Returns:
encoded string for a pattern such as "BranchInstruction".

pattern2string

private static final String pattern2string(String pattern)

pattern2string

private static final String pattern2string(String pattern,
                                           boolean make_string)

precompile

private static String precompile(short from,
                                 short to,
                                 short extra)

reread

public final void reread()
Reread the instruction list, e.g., after you've altered the list upon a match.

search

public final Iterator search(String pattern)
Start search beginning from the start of the given instruction list.
Parameters:
pattern - the instruction pattern to search for, where case is ignored
Returns:
iterator of matches where e.nextElement() returns an array of instruction handles describing the matched area

search

public final Iterator search(String pattern,
                             InstructionHandle from)
Start search beginning from `from'.
Parameters:
pattern - the instruction pattern to search for, where case is ignored
from - where to start the search in the instruction list
Returns:
iterator of matches where e.nextElement() returns an array of instruction handles describing the matched area

search

public final Iterator search(String pattern,
                             InstructionHandle from,
                             InstructionFinder.CodeConstraint constraint)
Search for the given pattern in the instruction list. You can search for any valid opcode via its symbolic name, e.g. "istore". You can also use a super class or an interface name to match a whole set of instructions, e.g. "BranchInstruction" or "LoadInstruction". "istore" is also an alias for all "istore_x" instructions. Additional aliases are "if" for "ifxx", "if_icmp" for "if_icmpxx", "if_acmp" for "if_acmpxx". Consecutive instruction names must be separated by white space which will be removed during the compilation of the pattern. For the rest the usual pattern matching rules for regular expressions apply.

Example pattern:

 search("BranchInstruction NOP ((IfInstruction|GOTO)+ ISTORE Instruction)*");
 

If you alter the instruction list upon a match such that other matching areas are affected, you should call reread() to update the finder and call search() again, because the matches are cached.

Parameters:
pattern - the instruction pattern to search for, where case is ignored
from - where to start the search in the instruction list
constraint - optional CodeConstraint to check the found code pattern for user-defined constraints
Returns:
iterator of matches where e.nextElement() returns an array of instruction handles describing the matched area

search

public final Iterator search(String pattern,
                             InstructionFinder.CodeConstraint constraint)
Start search beginning from the start of the given instruction list. Check found matches with the constraint object.
Parameters:
pattern - the instruction pattern to search for, case is ignored
constraint - constraints to be checked on matching code
Returns:
instruction handle or `null' if the match failed