Data flow analyzer doesn't execute all paths in some methods with subroutines
I have found that in some very unusual situations the data flow analysis
implemented in org.objectweb.asm.tree.analysis.Analyzer doesn't evaluate all
paths through the method.
I believe the problem is with how subroutines are being handled. The code that
deals with the JSR opcode merges the jump frame with the current frame, but the
jump instruction is not queued if the merge produces no changes.
Whilst this makes sense by itself the problem is that this means the RET
instruction (for returning from the subroutine) is not re-evaluated, meaning
that the checks that occur when the RET instruction is handled to see if the
instruction following the JSR (which is where the RET instruction returns the
control flow to) need to be re-evaluated are never performed.
This is a problem because if you have arrived at the JSR instruction with a new
frame state, even if you don't need to re-evaluate the subroutine, you do need
to re-evaluate the rest of the control flow continuing on after the return from
the subroutine.
I have a patch which appears to fix the problem for me, it basically does a
normal merge on the subsequent instruction if the subroutine is not going to be
re-evaluated (code starting at line 210).
if (insnOpcode == JSR) {
merge(jump, current, new Subroutine(j.label,
m.maxLocals, j));
// new code
if (!queued[jump]) {
// if the subroutine isn't going to be re-evaluated
// we still need to continue execution from
here as the frame state might be different
// this mimics what happens when we get the RET
instruction
// pop the value pushed by JSR
current.pop();
// check if the next instruction needs to be
re-evaluated
// we don't need to worry about merging the
results of the subroutine, because it wasn't re-evaluated!
merge(insn + 1, current, subroutine);
newControlFlowEdge(insn, insn + 1);
}
// end new code
} else {
merge(jump, current, subroutine);
}
Please note that this situation is very unusual and I have found only one or
two instances of it amongst tens of thousands of java methods.
One example I have is
org.apache.xpath.axes.FilterExprIteratorSimple.executeFilterExpr() from one
version of xalan. I will upload the exact version of xalan I am using in case
you want to test against exactly this case.