[Soot-list] Counting exits in a loop - understanding Jimple "goto [?= nop]"

[John Dean]

Hello all,
In Quentin's reply to my prior email, he noticed that my list of loop
statements didn't contain any instruction with the nested loop condition "k
< 2". That clue helped to narrow my focus in my method that generates a
loop's statements, and I think I've fixed the bug, and my program now
successfully counts the number of exits in each loop. Yeah!

Thanks for your important observation, Quentin!

In continuing to work on my dissertation project, I'm sure I'll have to
understand Jimple instructions better in order to solve some of my future
problems, so if anyone wants to try to answer my previous questions, that
would still be helpful. Here are simplified versions of 2 of my previous
questions:

1. I thought goto statements normally cause execution to jump to an address,
such that the address is sometimes represented by a label. But what do "goto
nop" and "goto [?= nop]" jump to? If nop is a label (and I doubt that's the
case), then isn't it a problem that there are more than one statement
(label?) with the nop label?

2. Any advice on Jimple documentation that might help me to understand
things better?

Thanks,
John

-----Original Message-----
From: soot-list-bounces at sable.mcgill.ca
[mailto:soot-list-bounces at sable.mcgill.ca] On Behalf Of John Dean
Sent: Monday, July 16, 2012 12:23 PM
To: 'Quentin Sabah'; soot-list at sable.mcgill.ca
Subject: Re: [Soot-list] Counting exits in a loop - understanding Jimple
"goto [?= nop]"

If anyone else wants to join in with help, feel free....

Hi Quentin,

Thanks for the reply.
Thanks for the tip on no k<2 instruction. That might be a clue in helping me
to figure out what's going on. I'll look into it.
I borrowed much of my find-the-loop-statements code from Hossein
Sadat-Hohtasham's Transcut program, and I think his program adds nop
instructions, but I'll look into that.

Question #1:
As you suggested, I read the JGotoStmt code
(http://opensourcejavaphp.net/java/soot/soot/jimple/internal/JGotoStmt.java.
html). I think I understand what you're saying about the goto statement, but
I still don't understand the goto statement fully. I thought goto statements
normally cause execution to jump to an address, such that the address is
sometimes represented by a label. But what do "goto nop" and "goto [?= nop]"
jump to? If nop is a label (and I doubt that's the case), then isn't it a
problem that there are more than one statements (labels?) with the nop
label?

The bottom line is that I need to understand how my "dumped" list of
statements in a loop represents 3 exits, so I can then debug my method that
finds the statements in a loop. In trying to help me, you asked "Can you
identify the 3 exits instruction precisely?" I've run my program on 3 test
loops (I provided 2 of the loops in my prior email, one was nested), and for
each loop, the number of found exits equals the number of "goto [?= nop]"
instructions near the end of its list of instructions. That result implies
(but does not prove) that each exit is generated by a "goto [?= nop]"
instruction near the end of an instruction list. Do you see the 3 "goto [?=
nop]" instructions near the end of the following instruction list?

[java] [nop, if j < 2 goto nop, nop, temp$8 = <java.lang.System:
java.io.PrintStream out>, temp$9 = new java.lang.StringBuffer, specialinvoke
temp$9.<java.lang.StringBuffer: void <init>()>(), nop, uniqueArgLocal1 = "J
= ", retval$2 = virtualinvoke temp$9.<java.lang.StringBuffer:
java.lang.StringBuffer append(java.lang.Object)>(uniqueArgLocal1), retval$3
= virtualinvoke temp$9.<java.lang.StringBuffer: java.lang.StringBuffer
append(int)>(j), temp$10 = virtualinvoke temp$9.<java.lang.StringBuffer:
java.lang.String toString()>(), virtualinvoke temp$8.<java.io.PrintStream:
void println(java.lang.String)>(temp$10), k = 0, nop, temp$11 =
<java.lang.System: java.io.PrintStream out>, temp$12 = new
java.lang.StringBuffer, specialinvoke temp$12.<java.lang.StringBuffer: void
<init>()>(), nop, uniqueArgLocal2 = "k = ", retval$4 = virtualinvoke
temp$12.<java.lang.StringBuffer: java.lang.StringBuffer
append(java.lang.Object)>(uniqueArgLocal2), retval$5 = virtualinvoke
temp$12.<java.lang.StringBuffer: java.lang.StringBuffer append(int)>(k),
temp$13 = virtualinvoke temp$12.<java.lang.StringBuffer: java.lang.String
toString()>(), virtualinvoke temp$11.<java.io.PrintStream: void
println(java.lang.String)>(temp$13), nop, temp$14 = k, temp$15 = temp$14 +
1, k = temp$15, goto [?= nop], goto [?= nop], nop, nop, temp$16 = j, temp$17
= temp$16 + 1, j = temp$17, goto [?= nop]]

Question #2:
Do you have any idea how those 3 instructions would be flagged as exits from
the loop?

For review purposes, here's the code to count the number of exits within a
loop's statements (it came from soot's Loop.getLoopExits(), so I think it's
correct):

for (Stmt s : loopStmts)
{
  for (Unit succ : g.getSuccsOf(s))
  {
    if (!loopStmts.contains(succ))
    {
      numOfExits++;
    }
  }
}

Once again, for review purposes, when I run my program on the following
sample loop, the program says that there are 3 exits in the outer loop and 1
exit in the inner loop:

for (int j=0; j<2; j++)
{
  System.out.println("J = " + j);
  for (int k=0; k<2; k++)
  {
    System.out.println("k = " + k);
  }
}

I think my program should say 1 exit in each loop. Thus, I'm trying to
figure out why it mistakenly says 3 exits in the outer loop instead of 1
exit.

I'm guessing that there's a bug in my program's generation of the loop's
statements, but it's hard to debug it when I don't understand the resulting
statements.

Question #3: Any advice on Jimple documentation that might help me to
understand things better?

Thanks,
John

-----Original Message-----
From: soot-list-bounces at sable.mcgill.ca
[mailto:soot-list-bounces at sable.mcgill.ca] On Behalf Of Quentin Sabah
Sent: Monday, July 16, 2012 8:17 AM
To: soot-list at sable.mcgill.ca
Subject: Re: [Soot-list] Counting exits in a loop - understanding Jimple
"goto [?= nop]"

Hi,
You strangely have a lot of "nop" instructions. And I cannot see any
instruction comparing k and 2 for the k<2 condition.

> 1. What is the meaning of "goto [?= nop]"
It means 'inconditional jump to instruction <string representation of the
target instruction>'.

Here, the execution continues to the next instruction (no branching), so it
is printed '[?= <TARGET TO STRING>]'.
You can read the code of JGotoStmt.toString() about that.

> 2. Any guidance on why there are 3 exits in the loop statements shown
above?
No sorry, the code dump is hardly readable. Can you identify the 3 exits
instruction precisely ?

--
Quentin Sabah, CIFRE Ph.D. student
Grenoble University
INRIA-SARDES                   | STMicroelectronics/AST
Montbonnot, France             | Grenoble, France
mailto:quentin.sabah at inria.fr  | mailto:quentin.sabah at st.com
phone: +33 476 61 52 42        | phone: +33 476 58 44 14
_______________________________________________
Soot-list mailing list
Soot-list at sable.mcgill.ca
http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list

_______________________________________________
Soot-list mailing list
Soot-list at sable.mcgill.ca
http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list