A Java Compiler Overview
Who Am I?








Shane A. Brewer
[email protected]
http://www.cs.ualberta.ca/~brewer
Masters Graduate Student
Supervisor: Dr. Nelson Amaral
Research: Using Method Specialization In Java Virtual
Machines for Method Devirtualization
Member of the U of A Swim Team
NOTE: Presentation Slides will be made available via
my web site.
October 21, 2003
Shane A. Brewer
2
This Lecture…



Will give an overview of the Java
Environment.
Discuss the differences in how compiler
optimizations are applied compared
with other languages (C, C++, etc)
Will give an overview of a toolset
developed specifically for Java (Soot)
October 21, 2003
Shane A. Brewer
3
Outline







A Brief Java Overview
Java Bytecode, Class files, and Bytecode
Compilers
Java Virtual Machines and Compilation
Techniques
Soot Overview
Soot Intermediate Representations
Soot Optimizations and Performance
Soot Eclipse Plugin Demonstration
October 21, 2003
Shane A. Brewer
4
Java History





First release of Java in 1996 by Sun Microsystems
The Java Language Specification by James Gosling
published in 1996
The Java Virtual Machine Specification by Tim
Lindholm and Frank Yelle published in 1996
Is now one of the most popular programming
languages, especially in enterprise development.
Java 1.5 to be released late 2003 and will include:




Auto Boxing/Unboxing
Enhanced For loops
Generics (Templates)
Enumerations
October 21, 2003
Shane A. Brewer
5
Java Overview








Is an object-oriented language that is
executed on a virtual machine
Originally designed for Internet-based usage
Combines procedural and object-oriented
features
Combines primitive data types and objects
Originally designed to be very portable
Strongly Typed
Supports Dynamic Class Loading
Built-in support for multi-threading
October 21, 2003
Shane A. Brewer
6
Java Environment [6]
October 21, 2003
Shane A. Brewer
7
Java Overview Continued
Java Source Files
Compiler Intermediate
Representation
Executable Machine
Code
int d = 2 + 3;
object.foo();
i0 := 2;
i1 := 3;
i2 := i0 + i2;
java.lang.Object.foo();
lw $s1, 100($s2)
add $s1, $s2, $s3
Java Classfiles
Java Bytecode
Compiler
October 21, 2003
i_const2
i_const3
iadd
invokevirtual #40
Shane A. Brewer
Java Virtual
Machine
8
The Java Platform [6]
October 21, 2003
Shane A. Brewer
9
A Java Program
class javaTest {
public static void main(String[] args) {
int x = stepPoly(6);
System.out.println(x);
} // End method main
October 21, 2003
public static int stepPoly(int x) {
if(x < 0) {
System.out.println("Bad Argument");
return -1;
} else if (x <= 5) {
return x * x;
} else {
return x * 5 + 16;
} // End if-else
} // End method stepPoly
} // End class javaTest
Shane A. Brewer
10
Dynamic Class Loading


Allows a new class to be loaded into the class
hierarchy at any point in execution
2 Ways This Is Done In Java

Class.forName() method gets the runtime class descriptor



User-defined Class Loaders allows a user to load classes in
custom ways (across a network, local, etc)
Good for program design



Class toRun = Class.forName(args[0]);
Lazy class loading
Dynamic installation of software
Bad for optimization
October 21, 2003
Shane A. Brewer
11
Dynamic Class Loading
Example
Can we make these
Method calls static?
Class A {
public void func() {
foo();
bar();
}
public void foo() {}
public void bar() {}
} // End Class A
Class B extends A {
…
} // End Class B
October 21, 2003
Shane A. Brewer
12
Dynamic Class Loading
Example
Can we make these
Method calls static?
Class A {
public void func() {
A.foo();
A.bar();
}
public void foo() {}
public void bar() {}
} // End Class A
Class B extends A {
…
} // End Class B
October 21, 2003
Shane A. Brewer
13
Dynamic Class Loading
Example
Class A {
public void func() {
A.foo();
A.bar();
public void foo() {}
public void bar() {}
}
} // End Class A
No! A class of type C can be loaded
at any point in program execution.
Consider an object objC of type C.
A method call objC.func() would result
in A.foo() and A.bar() incorrectly
being called.
October 21, 2003
Class B extends A {
…
} // End Class B
WRONG!!!
Class C extends B {
public void foo() {}
public void bar() {}
} // End Class C
Shane A. Brewer
14
Differences Between C++ and
Java






Java is run by a virtual machine
Java does not contain pointers (YAY!)
Java does not support generics (Will be
supported in version 1.5)
Java does not contain a preprocessor
Java only allows single inheritance.
Interfaces can be used to remedy this.
Java contains built-in multi-threaded tools.
October 21, 2003
Shane A. Brewer
15
Problems With Java

Relatively Slow execution?








Compilation done at run-time
Run-time exception checking
Optimizations have to deal with dynamic class loading
Slow execution can be offset by spending time optimizing
“hot” portions of code
Not pure object-oriented
No Generics (Version 1.5)
Everything is a reference
No const method arguments
October 21, 2003
Shane A. Brewer
16
Outline







A Brief Java Overview
Java Bytecode, Class files, and Bytecode
Compilers
Java Virtual Machines and Compilation
Techniques
Soot Overview
Soot Intermediate Representations
Soot Optimizations and Performance
Soot Eclipse Plugin Demonstration
October 21, 2003
Shane A. Brewer
17
The Java Bytecode Compiler




Converts Java source code to Java bytecode and into
Class files
Can be thought of a the “front end” of a traditional
compiler
Can perform a limited set of optimizations
Optimizations are harder to perform because:



Some bytecode instructions are high-level
Dynamic class loading
Examples:


Sun Microsystems: javac
IBM: Jikes
October 21, 2003
Shane A. Brewer
18
Java Bytecodes


Defined by the Java Virtual Machine
Instruction Set.
Are stack based



Most of the operators are typed


Keeps the instruction set compact
Facilitates implementation on architectures with
few or irregular registers.
iadd (Adds 2 integers together)
Some operators are not typed

dup (Duplicates the top value on the stack)
October 21, 2003
Shane A. Brewer
19
The Class file


Are not limited to the Java programming language
Is a file containing :






Java bytecodes
a definition of a single class or interface
Contains everything a JVM needs to know about the
particular class or interface.
Are strictly defined so JVM know what to expect
Are variable length
Contains 3 major parts:



Identification
Constant Pool
Detailed Information
October 21, 2003
Shane A. Brewer
20
October 21, 2003
Shane A. Brewer
21
A Java Program
public static void main(String[] args) {
int x = stepPoly(6);
System.out.println(x);
} // End method main
October 21, 2003
public static int stepPoly(int x) {
if(x < 0) {
System.out.println("Bad Argument");
return -1;
} else if (x <= 5) {
return x * x;
} else {
return x * 5 + 16;
} // End if-else
} // End method stepPoly
Shane A. Brewer
22
Java Bytecode
public static int stepPoly(int x) {
if(x < 0) {
System.out.println("Bad Argument");
return -1;
} else if (x <= 5) {
return x * x;
} else {
return x * 5 + 16;
} // End if-else
} // End method stepPoly
To obtain a listing of the bytecode from
a classfile, use the command:
javap –c <classfile>
October 21, 2003
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
int stepPoly(int);
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
16
iadd
ireturn
Shane A. Brewer
23
Java Bytecode
public static int stepPoly(int x) {
if(x < 0) {
System.out.println("Bad Argument");
return -1;
} else if (x <= 5) {
return x * x;
} else {
return x * 5 + 16;
} // End if-else
} // End method stepPoly
-Pushes an integer located at local
variable index 0 on the stack (the first
parameter to the method “x”)
-Sees if x (position 14 in the constant
pool) is greater than 0
October 21, 2003
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
int stepPoly(int);
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
16
iadd
ireturn
Shane A. Brewer
24
Java Bytecode
public static int stepPoly(int x) {
if(x < 0) {
System.out.println("Bad Argument");
return -1;
} else if (x <= 5) {
return x * x;
} else {
return x * 5 + 16;
} // End if-else
} // End method stepPoly
-Pushes the receiver object System.out
on to the stack.
-Pushes the parameter to the method
(String “Bad Argument) on the stack
-Invokes the virtual method
October 21, 2003
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
int stepPoly(int);
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
16
iadd
ireturn
Shane A. Brewer
25
Java Bytecode
public static int stepPoly(int x) {
if(x < 0) {
System.out.println("Bad Argument");
return -1;
} else if (x <= 5) {
return x * x;
} else {
return x * 5 + 16;
} // End if-else
} // End method stepPoly
-Pushes literal -1 on the stack
-Returns from the function with an
integer
October 21, 2003
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
int stepPoly(int);
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
16
iadd
ireturn
Shane A. Brewer
26
Java Bytecode
public static int stepPoly(int x) {
if(x < 0) {
System.out.println("Bad Argument");
return -1;
} else if (x <= 5) {
return x * x;
} else {
return x * 5 + 16;
} // End if-else
} // End method stepPoly
-Pushes integer from local variable at
index 0 (first parameter to the method)
-Pushes the constant 5 on the stack
-Compares the 2 values on the stack and
jumps to line 23 if x is greater than 5.
October 21, 2003
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
int stepPoly(int);
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
16
iadd
ireturn
Shane A. Brewer
27
Java Bytecode
public static int stepPoly(int x) {
if(x < 0) {
System.out.println("Bad Argument");
return -1;
} else if (x <= 5) {
return x * x;
} else {
return x * 5 + 16;
} // End if-else
} // End method stepPoly
-Load x on the stack (twice)
-Execute an integer multiplication and
push the result on the stack
-Return the result
October 21, 2003
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
int stepPoly(int);
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
16
iadd
ireturn
Shane A. Brewer
28
Java Bytecode
public static int stepPoly(int x) {
if(x < 0) {
System.out.println("Bad Argument");
return -1;
} else if (x <= 5) {
return x * x;
} else {
return x * 5 + 16;
} // End if-else
} // End method stepPoly
-Push x on the stack
-Push 5 on the stack
-Multiply the values and push the result
on the stack
-Push 16 on the stack
-Add the values and push the result
-Return the integer on the stack
October 21, 2003
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
int stepPoly(int);
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
16
iadd
ireturn
Shane A. Brewer
29
Outline







A Brief Java Overview
Java Bytecode, Class files, and Bytecode
Compilers
Java Virtual Machines and Compilation
Techniques
Soot Overview
Soot Intermediate Representations
Soot Optimizations and Performance
Soot Eclipse Plugin Demonstration
October 21, 2003
Shane A. Brewer
30
The Java Virtual Machine




Is an abstract computing machine
Only takes class files as input
Executes the corresponding bytecodes on the computer
architecture
Techniques are left up to the VM implementer:





Compilation
Optimization
Memory Management
Object Layout
Examples:



Sun Microsystems: Hot Spot
IBM: Jikes RVM
Blackdown: Blackdown VM (Linux)
October 21, 2003
Shane A. Brewer
31
Bytecode Translation Methods

Interpreted




Stack based
Done one bytecode at a time
SLOW!
Just-In-Time (JIT)




Bytecodes are compiled to native machine instructions when
they are executed.
Compilation only done once
Optimizations can take advantage of run-time profiling
Optimizations must be done during execution, making high
cost optimizations unattractive
October 21, 2003
Shane A. Brewer
32
Bytecode Translation Methods
Continued

Adaptive Just-In-Time





Similar to JIT compilers
Performs dynamic analysis to determine “hot” portions of
code and perform higher levels of optimization
Can also use analysis to determine which optimizations will
obtain the greatest speedup
Compilation can be done multiple times
Ahead-of-time (Way-Ahead-of-Time)




Compilation to native machine code is done by the bytecode
compiler, just like C++
Allows high cost optimizations to be performed
Portability is lost
Dynamic Class Loading is not permitted
October 21, 2003
Shane A. Brewer
33
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
Entering method stepPoly
imul
from call site:
ireturn
iload_0
iconst_5
int x = stepPoly(6);
imul
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
34
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
Pushes the integer located
ireturn
at index 0 in the local
iload_0
iconst_5
variable array on the stack
imul
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
6
35
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
Pops the stack and
iload_0
imul
determines if the value is
ireturn
greater than or equal to 0.
iload_0
iconst_5
If true, jump to the index
imul
in the byte array.
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
6
36
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
6 < 0?
if_icmpgt
23
iload_0
Pops the stack and
iload_0
imul
determines if the value is
ireturn
greater than or equal to 0.
iload_0
iconst_5
If true, jump to the index
imul
in the byte array.
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
6
37
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
Pops the stack and
iload_0
imul
determines if the value is
ireturn
greater than or equal to 0.
iload_0
iconst_5
If true, jump to the index
imul
in the byte array.
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
38
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
Pushes the integer located
ireturn
at index 0 in the local
iload_0
iconst_5
variable array on the stack
imul
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
6
39
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
Pushes the integer constant
ireturn
iload_0
5 on the stack
iconst_5
imul
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
5
6
40
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
The top 2 values on the
iload_0
iload_0
stack are popped and
imul
compared. If value 1 is
ireturn
iload_0
greater than value 2, control
iconst_5
transfers to the specified
imul
bipush
16
index in the byte array.
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
5
6
41
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
Is 6 < 5?
if_icmpgt
23
iload_0
iload_0
The top 2 values on the
imul
ireturn
stack are popped and
iload_0
compared. If value 1 is
iconst_5
imul
greater than value 2, control
bipush
16
transfers to the specified
iadd
ireturn
index in the byte array.
October 21, 2003
Shane A. Brewer
Stack
5 (Value 2)
6 (Value 1)
42
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
Is 6 < 5?
if_icmpgt
23
iload_0
iload_0
The top 2 values on the
imul
ireturn
stack are popped and
iload_0
compared. If value 1 is
iconst_5
imul
greater than value 2, control
bipush
16
transfers to the specified
iadd
ireturn
index in the byte array.
October 21, 2003
Shane A. Brewer
Stack
43
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
Pushes the integer located
ireturn
at index 0 in the local
iload_0
iconst_5
variable array on the stack
imul
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
6
44
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
Pushes the integer constant
ireturn
iload_0
5 on the stack
iconst_5
imul
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
5
6
45
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
Pop the top 2 values off of
imul
ireturn
the stack. Multiply them
iload_0
together and push the
iconst_5
imul
result on the stack
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
5
6
46
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
5 * 6 = 30
iload_0
iload_0
imul
ireturn
Pop the top 2 values off of
iload_0
iconst_5
the stack. Multiply them
imul
together and push the
bipush
16
iadd
result on the stack
ireturn
October 21, 2003
Shane A. Brewer
Stack
47
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
5 * 6 = 30
iload_0
iload_0
imul
ireturn
Pop the top 2 values off of
iload_0
iconst_5
the stack. Multiply them
imul
together and push the
bipush
16
iadd
result on the stack
ireturn
October 21, 2003
Shane A. Brewer
Stack
30
48
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
ireturn
Push the immediate byte
iload_0
(an integer) on to the stack.
iconst_5
imul
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
30
16
49
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
Pop the top 2 values from
imul
ireturn
the stack, add them
iload_0
together, and push the
iconst_5
imul
result on the stack.
bipush
16
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
30
16
50
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
30 + 16 = 46
if_icmpgt
23
iload_0
iload_0
imul
ireturn
Pop the top 2 values from
iload_0
iconst_5
the stack, add them
imul
together, and push the
bipush
16
iadd
result on the stack.
ireturn
October 21, 2003
Shane A. Brewer
Stack
51
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
30 + 16 = 46
if_icmpgt
23
iload_0
iload_0
imul
ireturn
Pop the top 2 values from
iload_0
iconst_5
the stack, add them
imul
together, and push the
bipush
16
iadd
result on the stack.
ireturn
October 21, 2003
Shane A. Brewer
Stack
46
52
Stack-based Interpretation
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
Local Variables Array
int stepPoly(int);
6
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
Pop the top value from the
iload_0
iload_0
stack from this method frame,
imul
and push the value on to the
ireturn
iload_0
stack of the caller method’s
iconst_5
stack. Any other values on
imul
bipush
16
the stack are discarded.
iadd
ireturn
October 21, 2003
Shane A. Brewer
Stack
46
53
Outline







A Brief Java Overview
Java Bytecode, Class files, and Bytecode
Compilers
Java Virtual Machines and Compilation
Techniques
Soot Overview
Soot Intermediate Representations
Soot Optimizations and Performance
Soot Eclipse Plugin Demonstration
October 21, 2003
Shane A. Brewer
54
What Is Soot?





A Java bytecode compiler written in
Java
Includes decompilation and visualization
Used to analyze and transform Java
bytecode
Comes as a command line tool or
Eclipse plugin
Output is an optimized class file
October 21, 2003
Shane A. Brewer
55
October 21, 2003
Shane A. Brewer
56
Outline







A Brief Java Overview
Java Bytecode, Class files, and Bytecode
Compilers
Java Virtual Machines and Compilation
Techniques
Soot Overview
Soot Intermediate Representations
Soot Optimizations and Performance
Soot Eclipse Plugin Demonstration
October 21, 2003
Shane A. Brewer
57
Soot Intermediate
Representations (IRs)





Baf: A stack representation without the
complexities of Java bytecode.
Jimple: A typed, 3-address code
representation of Java bytecode (Java
Simple)
Shrimple: An SSA-version of Jimple
Grimp: Like Jimple, but with aggregated
expressions.
Dava: A structured representation suitable for
Decompiling Java
October 21, 2003
Shane A. Brewer
58
Soot Intermediate
Representations
October 21, 2003
Shane A. Brewer
59
Baf: In Depth

Analysis and transformations on Java
bytecode is problematic for 2 reasons:




Encoding Issues
Untyped Bytecodes
A stack based representation
Easier to manipulate as it is fully typed
October 21, 2003
Shane A. Brewer
60
Previous Example
Refer back to our Java example
public static void main(String[] args) {
int x = stepPoly(6);
System.out.println(x);
} // End method main
October 21, 2003
public static int stepPoly(int x) {
if(x < 0) {
System.out.println("Bad Argument");
return -1;
} else if (x <= 5) {
return x * x;
} else {
return x * 5 + 16;
} // End if-else
} // End method stepPoly
Shane A. Brewer
61
Previous Example
public static int stepPoly(int x) {
if(x < 0) {
System.out.println("Bad Argument");
return -1;
} else if (x <= 5) {
return x * x;
} else {
return x * 5 + 16;
} // End if-else
} // End method stepPoly
Java method with corresponding
bytecode
October 21, 2003
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
int stepPoly(int);
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
16
iadd
ireturn
Shane A. Brewer
62
Bytecode and Corresponding
Baf
public static
Code:
0:
1:
4:
7:
9:
12:
13:
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
public static int stepPoly(int)
{
word i0;
int stepPoly(int);
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
iload_0
iconst_5
if_icmpgt
23
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
16
iadd
ireturn
October 21, 2003
i0 := @parameter0: int;
load.i i0;
ifge label0;
staticget <java.lang.System: java.io.PrintStream out>;
push "Bad Arugument";
virtualinvoke <java.io.PrintStream: void println(java.lang.String)>;
push -1;
return.i;
label0:
load.i i0;
push 5;
ifcmpgt.i label1;
load.i i0;
load.i i0;
mul.i;
return.i;
label1:
load.i i0;
push 5;
mul.i;
push 16;
add.i;
return.i;
}
Shane A. Brewer
63
Bytecode and Corresponding
Baf: Broken Up
word i0;
0:
1:
4:
iload_0
ifge
getstatic
7:
9:
12:
13:
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
i0 := @parameter0: int;
load.i i0;
ifge label0;
staticget <java.lang.System: java.io.PrintStream out>;
push "Bad Arugument";
virtualinvoke <java.io.PrintStream:
void println(java.lang.String)>;
push -1;
return.i;
The baf file starts off with variable declarations. A prefix of “r” refers to a general
purpose variable while an “i” refers a variable that stores an integer.
October 21, 2003
Shane A. Brewer
64
Bytecode and Corresponding
Baf: Broken Up
word i0;
0:
1:
4:
7:
9:
12:
13:
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
i0 := @parameter0: int;
load.i i0;
ifge label0;
staticget <java.lang.System: java.io.PrintStream out>;
push "Bad Arugument";
virtualinvoke <java.io.PrintStream:
void println(java.lang.String)>;
push -1;
return.i;
-The first instruction takes the first parameter to the method and stores it in
variable i0.
-The second instruction loads in the value of variable i0 and push it on the stack.
October 21, 2003
Shane A. Brewer
65
Bytecode and Corresponding
Baf: Broken Up
word i0;
0:
1:
4:
iload_0
ifge
getstatic
7:
9:
12:
13:
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
i0 := @parameter0: int;
load.i i0;
ifge label0;
staticget <java.lang.System: java.io.PrintStream out>;
push "Bad Arugument";
virtualinvoke <java.io.PrintStream:
void println(java.lang.String)>;
push -1;
return.i;
-Here, the if-greater-than-or-equal is replaced by a label, rather than an index into
the bytecode array. Note that the label is not shown in this snippet.
October 21, 2003
Shane A. Brewer
66
Bytecode and Corresponding
Baf: Broken Up
word i0;
0:
1:
4:
iload_0
ifge
getstatic
7:
9:
12:
13:
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
i0 := @parameter0: int;
load.i i0;
ifge label0;
staticget <java.lang.System: java.io.PrintStream out>;
push "Bad Arugument";
virtualinvoke <java.io.PrintStream:
void println(java.lang.String)>;
push -1;
return.i;
-The first instruction obtains the receiver object of the static method
“java.io.PrintStream.println”. Here, the receiver object is the class
“java.lang.System.out” where the type of “out” is “java.io.PrintStream”.
-The second instruction pushes the first argument to the method on the stack. In
this case it is the string “Bad Argument”.
-The last instruction invokes the virtual method “java.io.PrintStream” with a return
value of void, and a single argument of type “java.lang.String”
October 21, 2003
Shane A. Brewer
67
Bytecode and Corresponding
Baf: Broken Up
word i0;
0:
1:
4:
7:
9:
12:
13:
iload_0
ifge
getstatic
14
#25; //Field java/lang/System.out:
Ljava/io/PrintStream;
ldc
#37; //String Bad Argument
invokevirtual #40; //Method java/io/PrintStream.println:
(Ljava/lang/String;)V
iconst_m1
ireturn
i0 := @parameter0: int;
load.i i0;
ifge label0;
staticget <java.lang.System: java.io.PrintStream out>;
push "Bad Arugument";
virtualinvoke <java.io.PrintStream:
void println(java.lang.String)>;
push -1;
return.i;
-The constant -1 is pushed on to the stack
-The method exits, returning a integer located on the top of the stack
October 21, 2003
Shane A. Brewer
68
Bytecode and Corresponding
Baf
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
iload_0
iconst_5
if_icmpgt
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
iadd
ireturn
label0:
load.i i0;
push 5;
ifcmpgt.i label1;
load.i i0;
load.i i0;
mul.i;
return.i;
label1:
load.i i0;
push 5;
mul.i;
push 16;
add.i;
return.i;
23
16
-Targets of gotos are specifically labeled in Baf
October 21, 2003
Shane A. Brewer
69
Bytecode and Corresponding
Baf
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
iload_0
iconst_5
if_icmpgt
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
iadd
ireturn
23
16
label0:
load.i i0;
push 5;
ifcmpgt.i label1;
load.i i0;
load.i i0;
mul.i;
return.i;
label1:
load.i i0;
push 5;
mul.i;
push 16;
add.i;
return.i;
-An integer (The first argument to the method) is pushed on the stack. Remember that
we stored the first argument into variable i0 in the previous snippet.
-The constant 5 is pushed on the stack
-A comparison of the top 2 values on the stack are compared. Note the difference
between the target of the gotos if the test succeeds.
October 21, 2003
Shane A. Brewer
70
Bytecode and Corresponding
Baf
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
iload_0
iconst_5
if_icmpgt
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
iadd
ireturn
23
16
label0:
load.i i0;
push 5;
ifcmpgt.i label1;
load.i i0;
load.i i0;
mul.i;
return.i;
label1:
load.i i0;
push 5;
mul.i;
push 16;
add.i;
return.i;
-The first argument is pushed on to the stack twice (not much difference)
-Integer multiplication is performed
-The top value on the stack (an integer) is returned
October 21, 2003
Shane A. Brewer
71
Bytecode and Corresponding
Baf
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
iload_0
iconst_5
if_icmpgt
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
iadd
ireturn
23
16
label0:
load.i i0;
push 5;
ifcmpgt.i label1;
load.i i0;
load.i i0;
mul.i;
return.i;
label1:
load.i i0;
push 5;
mul.i;
push 16;
add.i;
return.i;
-Argument is loaded again
-The constant 5 is pushed on the stack
-Integer multiplication is done. Result is pushed on the stack
October 21, 2003
Shane A. Brewer
72
Bytecode and Corresponding
Baf
14:
15:
16:
19:
20:
21:
22:
23:
24:
25:
26:
28:
29:
iload_0
iconst_5
if_icmpgt
iload_0
iload_0
imul
ireturn
iload_0
iconst_5
imul
bipush
iadd
ireturn
23
16
label0:
load.i i0;
push 5;
ifcmpgt.i label1;
load.i i0;
load.i i0;
mul.i;
return.i;
label1:
load.i i0;
push 5;
mul.i;
push 16;
add.i;
return.i;
-The constant 16 is pushed on the stack
-Integer addition is performed on the top 2 values on the stack
-The method returns the top value on the stack (An integer)
October 21, 2003
Shane A. Brewer
73
Jimple: In Depth

Optimizing stack code is awkward







Expression are not explicit; An instruction may have it’s
operands separated by an arbitrary number of stack
instructions
Stack is untyped by nature
Jimple is a 3-address code representation of
bytecode
Typed
Is ideal for performing optimizations and analysis
Operators are untyped
Local variables are given explicit primitive, class, or
interface types
October 21, 2003
Shane A. Brewer
74
Baf and Corresponding Jimple
public static int stepPoly(int)
{
word i0;
i0 := @parameter0: int;
load.i i0;
ifge label0;
staticget <java.lang.System: java.io.PrintStream out>;
push "Bad Arugument";
virtualinvoke <java.io.PrintStream: void println(java.lang.String)>;
push -1;
return.i;
label0:
load.i i0;
push 5;
ifcmpgt.i label1;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
$r0 = <java.lang.System: java.io.PrintStream out>;
virtualinvoke $r0.<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
label0:
if i0 > 5 goto label1;
load.i i0;
load.i i0;
mul.i;
return.i;
label1:
load.i i0;
push 5;
mul.i;
push 16;
add.i;
return.i;
}
public static int stepPoly(int)
{
int i0, $i1, $i2, $i3;
java.io.PrintStream $r0;
$i1 = i0 * i0;
return $i1;
label1:
$i2 = i0 * 5;
$i3 = $i2 + 16;
return $i3;
}
October 21, 2003
Shane A. Brewer
75
Baf and Corresponding Jimple
word i0;
i0 := @parameter0: int;
load.i i0;
ifge label0;
staticget <java.lang.System: java.io.PrintStream out>;
push "Bad Arugument";
virtualinvoke <java.io.PrintStream:
void println(java.lang.String)>;
push -1;
return.i;
int i0, $i1, $i2, $i3;
java.io.PrintStream $r0;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
$r0 = <java.lang.System: java.io.PrintStream out>;
virtualinvoke $r0.<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
-Variable declarations come first. In Jimple, variables prefixed with a “$” refer to a
stack position.
-Variables i0, $i1, $i2, $i3 are typed as integers.
-Variable $r0 is typed as java.io.PrintStream
October 21, 2003
Shane A. Brewer
76
Baf and Corresponding Jimple
word i0;
i0 := @parameter0: int;
load.i i0;
ifge label0;
staticget <java.lang.System: java.io.PrintStream out>;
push "Bad Arugument";
virtualinvoke <java.io.PrintStream:
void println(java.lang.String)>;
push -1;
return.i;
int i0, $i1, $i2, $i3;
java.io.PrintStream $r0;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
$r0 = <java.lang.System: java.io.PrintStream out>;
virtualinvoke $r0.<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
-Variable i0 gets the value of the first parameter to the method.
-The if check is reduced to a single instruction, compared with 2 stack-based instructions.
Goto and labels remain the same.
October 21, 2003
Shane A. Brewer
77
Baf and Corresponding Jimple
word i0;
i0 := @parameter0: int;
load.i i0;
ifge label0;
staticget <java.lang.System: java.io.PrintStream out>;
push "Bad Arugument";
virtualinvoke <java.io.PrintStream:
void println(java.lang.String)>;
push -1;
return.i;
int i0, $i1, $i2, $i3;
java.io.PrintStream $r0;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
$r0 = <java.lang.System: java.io.PrintStream out>;
virtualinvoke $r0.<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
-The receiver of the method call “java.io.PrintStream” is stored in variable $r0. Note
that in Baf, this was a stack position.
-The virtual method “println” is invoked on the object stored in $r0.
-The constant -1 is returned from the method.
October 21, 2003
Shane A. Brewer
78
Baf and Corresponding Jimple
label0:
load.i i0;
push 5;
ifcmpgt.i label1;
load.i i0;
load.i i0;
mul.i;
return.i;
label0:
if i0 > 5 goto label1;
$i1 = i0 * i0;
return $i1;
label1:
$i2 = i0 * 5;
$i3 = $i2 + 16;
return $i3;
label1:
load.i i0;
push 5;
mul.i;
push 16;
add.i;
return.i;
}
-The if statement is reduced from 3 Baf instructions to 1 Jimple instruction.
October 21, 2003
Shane A. Brewer
79
Baf and Corresponding Jimple
label0:
load.i i0;
push 5;
ifcmpgt.i label1;
load.i i0;
load.i i0;
mul.i;
return.i;
label0:
if i0 > 5 goto label1;
$i1 = i0 * i0;
return $i1;
label1:
$i2 = i0 * 5;
$i3 = $i2 + 16;
return $i3;
label1:
load.i i0;
push 5;
mul.i;
push 16;
add.i;
return.i;
}
-The multiplication operation is no longer typed in Jimple.
-The variable $i1 refers to the result of the multiplication operation that was a stack
position.
October 21, 2003
Shane A. Brewer
80
Baf and Corresponding Jimple
label0:
load.i i0;
push 5;
ifcmpgt.i label1;
load.i i0;
load.i i0;
mul.i;
return.i;
label0:
if i0 > 5 goto label1;
$i1 = i0 * i0;
return $i1;
label1:
$i2 = i0 * 5;
$i3 = $i2 + 16;
return $i3;
label1:
load.i i0;
push 5;
mul.i;
push 16;
add.i;
return.i;
}
-The results of the multiplication and addition operations are stored in the $i2 and $i3
variables. These are stack positions in Baf.
October 21, 2003
Shane A. Brewer
81
Grimp: In Depth

3 address code is sometimes harder to deal
with than complex structures.





Generating stack code is simpler with large
expressions.
Grimp is an unstructured representation
which allows trees to be constructed for
expressions.
Easy to read
Used for the foundation of a decompiler.
Similar to the original Java code.
October 21, 2003
Shane A. Brewer
82
Jimple and Corresponding
Grimp
public static int stepPoly(int)
{
int i0, $i1, $i2, $i3;
java.io.PrintStream $r0;
public static int stepPoly(int)
{
int i0;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
$r0 = <java.lang.System: java.io.PrintStream out>;
virtualinvoke $r0.<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
<java.lang.System: java.io.PrintStream out>.
<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
label0:
if i0 > 5 goto label1;
$i1 = i0 * i0;
return $i1;
label1:
$i2 = i0 * 5;
$i3 = $i2 + 16;
return $i3;
}
October 21, 2003
label0:
if i0 > 5 goto label1;
return i0 * i0;
label1:
return i0 * 5 + 16;
}
Shane A. Brewer
83
Jimple and Corresponding
Grimp
int i0, $i1, $i2, $i3;
java.io.PrintStream $r0;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
$r0 = <java.lang.System: java.io.PrintStream out>;
virtualinvoke $r0.<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
int i0;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
<java.lang.System: java.io.PrintStream out>.
<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
-Only one variable is needed as the operations are aggregated together.
October 21, 2003
Shane A. Brewer
84
Jimple and Corresponding
Grimp
int i0;
int i0, $i1, $i2, $i3;
java.io.PrintStream $r0;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
$r0 = <java.lang.System: java.io.PrintStream out>;
virtualinvoke $r0.<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
<java.lang.System: java.io.PrintStream out>.
<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
-These instructions stay the same.
October 21, 2003
Shane A. Brewer
85
Jimple and Corresponding
Grimp
int i0, $i1, $i2, $i3;
java.io.PrintStream $r0;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
$r0 = <java.lang.System: java.io.PrintStream out>;
virtualinvoke $r0.<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
int i0;
i0 := @parameter0: int;
if i0 >= 0 goto label0;
<java.lang.System: java.io.PrintStream out>.
<java.io.PrintStream:
void println(java.lang.String)>("Bad Arugument");
return -1;
-The receiver object “java.lang.System.out” is hard coded in the method call instruction
along with the argument.
October 21, 2003
Shane A. Brewer
86
Jimple and Corresponding
Grimp
label0:
if i0 > 5 goto label1;
$i1 = i0 * i0;
return $i1;
label0:
if i0 > 5 goto label1;
return i0 * i0;
label1:
$i2 = i0 * 5;
$i3 = $i2 + 16;
return $i3;
label1:
return i0 * 5 + 16;
-Instructions are aggregated together into a single instruction.
October 21, 2003
Shane A. Brewer
87
Outline







A Brief Java Overview
Java Bytecode, Class files, and Bytecode
Compilers
Java Virtual Machines and Compilation
Techniques
Soot Overview
Soot Intermediate Representations
Soot Optimizations and Performance
Soot Eclipse Plugin Demonstration
October 21, 2003
Shane A. Brewer
88
Soot Optimizations








Common Subexpression Elimination
Busy Code Motion
Lazy Code Motion
Copy Propagation
Constant Propagation
Dead Assignment Elimination
Unreachable Code Elimination
Unconditional Branch Folding
October 21, 2003
Shane A. Brewer
89
Soot Perfomance



Changing bytecode to Baf, then Jimple, the
Grimp, and then back to Bytecode with no
optimizations reduces performance by only
2%.
With whole program optimizations turned on,
speedups of 21% were found for SPECjvm98.
Using the attributes extension, programs
exhibited speedups of approximately 8%
(Some with slowdown)
October 21, 2003
Shane A. Brewer
90
Summary



Java offers new challenges for
compilers at both the classfile level and
the virtual machine level.
Soot offers a set of tools to optimize
classfiles.
Will Java become faster than other
languages? (C, C++, etc)
October 21, 2003
Shane A. Brewer
91
References
1.
2.
3.
4.
5.
6.
http://www.sable.mcgill.ca/soot
http://www.eclipse.org
P. Pominville, F. Qian, R. Vallee-Rai, L. Hendren, and C.
Verbrugge, “A Gramework For Optimizing Java Using
Attributes”, Lecture Notes In Computer Science, 2001.
R. Vallee-Rai, P. Co, E. Gagnon, L. Hendren, P. Lam, and V.
Sundaresan, “Soot – A Java Bytecode Optimization
Framework”, Proceedings of CASCON '99, 1999.
R. Vallee-Rai, E. Gagnon, L. Hendren, P. Lam, P. Pominville,
and V. Sundaresan, “Optimizing Java Bytecode Using The Soot
Gramework: Is It Feasible?”, Computational Complexity, 2000.
Bill Venners, “Inside the Java 2 Virtual Machine”, McGraw-Hill
Osborne Media, 2000.
October 21, 2003
Shane A. Brewer
92
Outline







A Brief Java Overview
Java Bytecode, Class files, and Bytecode
Compilers
Java Virtual Machines and Compilation
Techniques
Soot Overview
Soot Intermediate Representations
Soot Optimizations and Performance
Soot Eclipse Plugin Demonstration
October 21, 2003
Shane A. Brewer
93
Descargar

Soot: A Java Optimization Framework