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

[John Dean]

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