Subroutinespublic class Subroutines extends Object | Instances of this class contain information about the subroutines
found in a code array of a method.
This implementation considers the top-level (the instructions
reachable without a JSR or JSR_W starting off from the first
instruction in a code array of a method) being a special subroutine;
see getTopLevel() for that.
Please note that the definition of subroutines in the Java Virtual
Machine Specification, Second Edition is somewhat incomplete.
Therefore, JustIce uses an own, more rigid notion.
Basically, a subroutine is a piece of code that starts at the target
of a JSR of JSR_W instruction and ends at a corresponding RET
instruction. Note also that the control flow of a subroutine
may be complex and non-linear; and that subroutines may be nested.
JustIce also mandates subroutines not to be protected by exception
handling code (for the sake of control flow predictability).
To understand JustIce's notion of subroutines, please read
TODO: refer to the paper. |
| Fields Summary |
|---|
| private Hashtable | subroutinesThe Hashtable containing the subroutines found.
Key: InstructionHandle of the leader of the subroutine.
Elements: SubroutineImpl objects. | | public final Subroutine | TOPLEVELThis is referring to a special subroutine, namely the
top level. This is not really a subroutine but we use
it to distinguish between top level instructions and
unreachable instructions. |
| Constructors Summary |
|---|
public Subroutines(MethodGen mg)Constructor.
InstructionHandle[] all = mg.getInstructionList().getInstructionHandles();
CodeExceptionGen[] handlers = mg.getExceptionHandlers();
// Define our "Toplevel" fake subroutine.
TOPLEVEL = new SubroutineImpl();
// Calculate "real" subroutines.
HashSet sub_leaders = new HashSet(); // Elements: InstructionHandle
InstructionHandle ih = all[0];
for (int i=0; i<all.length; i++){
Instruction inst = all[i].getInstruction();
if (inst instanceof JsrInstruction){
sub_leaders.add(((JsrInstruction) inst).getTarget());
}
}
// Build up the database.
Iterator iter = sub_leaders.iterator();
while (iter.hasNext()){
SubroutineImpl sr = new SubroutineImpl();
InstructionHandle astore = (InstructionHandle) (iter.next());
sr.setLocalVariable( ((ASTORE) (astore.getInstruction())).getIndex() );
subroutines.put(astore, sr);
}
// Fake it a bit. We want a virtual "TopLevel" subroutine.
subroutines.put(all[0], TOPLEVEL);
sub_leaders.add(all[0]);
// Tell the subroutines about their JsrInstructions.
// Note that there cannot be a JSR targeting the top-level
// since "Jsr 0" is disallowed in Pass 3a.
// Instructions shared by a subroutine and the toplevel are
// disallowed and checked below, after the BFS.
for (int i=0; i<all.length; i++){
Instruction inst = all[i].getInstruction();
if (inst instanceof JsrInstruction){
InstructionHandle leader = ((JsrInstruction) inst).getTarget();
((SubroutineImpl) getSubroutine(leader)).addEnteringJsrInstruction(all[i]);
}
}
// Now do a BFS from every subroutine leader to find all the
// instructions that belong to a subroutine.
HashSet instructions_assigned = new HashSet(); // we don't want to assign an instruction to two or more Subroutine objects.
Hashtable colors = new Hashtable(); //Graph colouring. Key: InstructionHandle, Value: java.awt.Color .
iter = sub_leaders.iterator();
while (iter.hasNext()){
// Do some BFS with "actual" as the root of the graph.
InstructionHandle actual = (InstructionHandle) (iter.next());
// Init colors
for (int i=0; i<all.length; i++){
colors.put(all[i], Color.white);
}
colors.put(actual, Color.gray);
// Init Queue
ArrayList Q = new ArrayList();
Q.add(actual); // add(Obj) adds to the end, remove(0) removes from the start.
/* BFS ALGORITHM MODIFICATION: Start out with multiple "root" nodes, as exception handlers are starting points of top-level code, too. [why top-level? TODO: Refer to the special JustIce notion of subroutines.]*/
if (actual == all[0]){
for (int j=0; j<handlers.length; j++){
colors.put(handlers[j].getHandlerPC(), Color.gray);
Q.add(handlers[j].getHandlerPC());
}
}
/* CONTINUE NORMAL BFS ALGORITHM */
// Loop until Queue is empty
while (Q.size() != 0){
InstructionHandle u = (InstructionHandle) Q.remove(0);
InstructionHandle[] successors = getSuccessors(u);
for (int i=0; i<successors.length; i++){
if (((Color) colors.get(successors[i])) == Color.white){
colors.put(successors[i], Color.gray);
Q.add(successors[i]);
}
}
colors.put(u, Color.black);
}
// BFS ended above.
for (int i=0; i<all.length; i++){
if (colors.get(all[i]) == Color.black){
((SubroutineImpl) (actual==all[0]?getTopLevel():getSubroutine(actual))).addInstruction(all[i]);
if (instructions_assigned.contains(all[i])){
throw new StructuralCodeConstraintException("Instruction '"+all[i]+"' is part of more than one subroutine (or of the top level and a subroutine).");
}
else{
instructions_assigned.add(all[i]);
}
}
}
if (actual != all[0]){// If we don't deal with the top-level 'subroutine'
((SubroutineImpl) getSubroutine(actual)).setLeavingRET();
}
}
// Now make sure no instruction of a Subroutine is protected by exception handling code
// as is mandated by JustIces notion of subroutines.
for (int i=0; i<handlers.length; i++){
InstructionHandle _protected = handlers[i].getStartPC();
while (_protected != handlers[i].getEndPC().getNext()){// Note the inclusive/inclusive notation of "generic API" exception handlers!
Enumeration subs = subroutines.elements();
while (subs.hasMoreElements()){
Subroutine sub = (Subroutine) subs.nextElement();
if (sub != subroutines.get(all[0])){ // We don't want to forbid top-level exception handlers.
if (sub.contains(_protected)){
throw new StructuralCodeConstraintException("Subroutine instruction '"+_protected+"' is protected by an exception handler, '"+handlers[i]+"'. This is forbidden by the JustIce verifier due to its clear definition of subroutines.");
}
}
}
_protected = _protected.getNext();
}
}
// Now make sure no subroutine is calling a subroutine
// that uses the same local variable for the RET as themselves
// (recursively).
// This includes that subroutines may not call themselves
// recursively, even not through intermediate calls to other
// subroutines.
noRecursiveCalls(getTopLevel(), new HashSet());
|
| Methods Summary |
|---|
| public Subroutine | getSubroutine(com.sun.org.apache.bcel.internal.generic.InstructionHandle leader)Returns the Subroutine object associated with the given
leader (that is, the first instruction of the subroutine).
You must not use this to get the top-level instructions
modeled as a Subroutine object.
Subroutine ret = (Subroutine) subroutines.get(leader);
if (ret == null){
throw new AssertionViolatedException("Subroutine requested for an InstructionHandle that is not a leader of a subroutine.");
}
if (ret == TOPLEVEL){
throw new AssertionViolatedException("TOPLEVEL special subroutine requested; use getTopLevel().");
}
return ret;
| | private static com.sun.org.apache.bcel.internal.generic.InstructionHandle[] | getSuccessors(com.sun.org.apache.bcel.internal.generic.InstructionHandle instruction)A utility method that calculates the successors of a given InstructionHandle
in the same subroutine. That means, a RET does not have any successors
as defined here. A JsrInstruction has its physical successor as its successor
(opposed to its target) as defined here.
final InstructionHandle[] empty = new InstructionHandle[0];
final InstructionHandle[] single = new InstructionHandle[1];
final InstructionHandle[] pair = new InstructionHandle[2];
Instruction inst = instruction.getInstruction();
if (inst instanceof RET){
return empty;
}
// Terminates method normally.
if (inst instanceof ReturnInstruction){
return empty;
}
// Terminates method abnormally, because JustIce mandates
// subroutines not to be protected by exception handlers.
if (inst instanceof ATHROW){
return empty;
}
// See method comment.
if (inst instanceof JsrInstruction){
single[0] = instruction.getNext();
return single;
}
if (inst instanceof GotoInstruction){
single[0] = ((GotoInstruction) inst).getTarget();
return single;
}
if (inst instanceof BranchInstruction){
if (inst instanceof Select){
// BCEL's getTargets() returns only the non-default targets,
// thanks to Eli Tilevich for reporting.
InstructionHandle[] matchTargets = ((Select) inst).getTargets();
InstructionHandle[] ret = new InstructionHandle[matchTargets.length+1];
ret[0] = ((Select) inst).getTarget();
System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length);
return ret;
}
else{
pair[0] = instruction.getNext();
pair[1] = ((BranchInstruction) inst).getTarget();
return pair;
}
}
// default case: Fall through.
single[0] = instruction.getNext();
return single;
| | public Subroutine | getTopLevel()For easy handling, the piece of code that is not a
subroutine, the top-level, is also modeled as a Subroutine
object.
It is a special Subroutine object where you must not invoke
getEnteringJsrInstructions() or getLeavingRET().
return TOPLEVEL;
| | private void | noRecursiveCalls(Subroutine sub, java.util.HashSet set)This (recursive) utility method makes sure that
no subroutine is calling a subroutine
that uses the same local variable for the RET as themselves
(recursively).
This includes that subroutines may not call themselves
recursively, even not through intermediate calls to other
subroutines.
Subroutine[] subs = sub.subSubs();
for (int i=0; i<subs.length; i++){
int index = ((RET) (subs[i].getLeavingRET().getInstruction())).getIndex();
if (!set.add(new Integer(index))){
// Don't use toString() here because of possibly infinite recursive subSubs() calls then.
SubroutineImpl si = (SubroutineImpl) subs[i];
throw new StructuralCodeConstraintException("Subroutine with local variable '"+si.localVariable+"', JSRs '"+si.theJSRs+"', RET '"+si.theRET+"' is called by a subroutine which uses the same local variable index as itself; maybe even a recursive call? JustIce's clean definition of a subroutine forbids both.");
}
noRecursiveCalls(subs[i], set);
set.remove(new Integer(index));
}
| | public Subroutine | subroutineOf(com.sun.org.apache.bcel.internal.generic.InstructionHandle any)Returns the subroutine object associated with the
given instruction. This is a costly operation, you
should consider using getSubroutine(InstructionHandle).
Returns 'null' if the given InstructionHandle lies
in so-called 'dead code', i.e. code that can never
be executed.
Iterator i = subroutines.values().iterator();
while (i.hasNext()){
Subroutine s = (Subroutine) i.next();
if (s.contains(any)) return s;
}
System.err.println("DEBUG: Please verify '"+any+"' lies in dead code.");
return null;
//throw new AssertionViolatedException("No subroutine for InstructionHandle found (DEAD CODE?).");
| | public java.lang.String | toString()Returns a String representation of this object; merely for debugging puposes.
return "---\n"+subroutines.toString()+"\n---\n";
|
|
