CODEWITHSUNDEEP
if-statementwhile-loopjvmbytecodecontrol-flow-graph
Mikaël Mayer
Mikaël Mayer

Reputation: 10681

Can all control flow graphs be translated back using if and while?

I was wondering if all control flow graphs obtained from a typical JVM bytecode (see how to) of a single method (no recursion allowed) could be translated back to equivalent ifs and whiles code.

If not, what is the smallest JVM bytecode sequence which cannot be translated back to ifs and whiles ?

Upvotes: 3

Views: 686

Answers (2)

Antimony
Antimony

Reputation: 39441

There are several reasons why bytecode control flow may not be translatable back into Java without extreme measures.

  • JSR/RET - this instruction pairs has no equivalent in Java. The best you can do is inline it. However, this will lead to an exponential increase in code size if they are nested.

  • Irreducible loops - In Java, every loop has a single entry point which dominates the rest of the loop. An "irreducible" loop is one that has multiple distinct entry points, and hence no direct Java equivalent. There are several approaches. My preferred solution is to duplicate part of the loop body, though this can lead to exponential blow up in pathological cases as well. The other approach is to turn the method into a while-switch state machine, but this obscures the original control flow.

An example instruction sequence is

ifnull L3
L2: nop
L3: goto L2

This is the simplest possible irreducible loop. It is impossible to turn into Java without changing the structure or duplicating part of the code (though in this case, there are no actual statements so duplicating wouldn't be so bad).

  • The last part is exception handling. Java requires all exception handling to be done through structured try/catch blocks and it's variations while bytecode doesn't. At the bytecode level, exception handlers are basically another form of goto. In pathological cases, the best you can do is create a seperate try catch for every instruction that throws and repeat the process above.

Upvotes: 6

Andrey Breslav
Andrey Breslav

Reputation: 25757

I think a jump into the middle of a loop is not expressible in structured code:

JMP L1 // jump into the middle of a loop
L2:
IFCMP L3 // loop condition
// do something inside the loop
L1:
// do something else inside the loop
JMP L2
L3:
// exit the loop

Sorry, this is not exactly JVM bytecode, but you can get the idea.

Upvotes: 1

Related Questions