[Soot-list] some performance tweaks for Jimple construction
Manu Sridharan
manu_s at eecs.berkeley.edu
Mon Jan 30 18:55:20 EST 2006
Hi there,
I spent some time over the weekend looking for simple changes to speed
up construction of Jimple, as it is often a bottleneck when I'm running
experiments. I found two relatively small changes that seemed to speed
things up for me by about 20% or so; they are in the attached patch (to
be applied from the src/ sub-directory). The changes are:
1. Implemented parent and child pointers in the TypeVariable classes
more efficiently
2. Change SmartLocalDefs to use BitSets rather than HashSets for
representing flow facts
I have hardly tested these changes at all; is there some sort of
regression test I can run to see if they broke anything? A couple of
other notes:
- I'm attaching an ArraySet class that I wrote myself, as the
soot.util.ArraySet class seemed to be buggy when I used it (didn't spend
time tracking down the bugs). I'm glad to contribute my class to Soot
under the appropriate open-source license if it's useful.
- In SmartLocalDefs, I use some methods of BitSet that were introduced
in the 1.4 API. This may not be acceptable if Soot is supposed to be
compatible with earlier JVM versions.
- I didn't test to see if the changes significantly impact memory
consumption, but I doubt it.
Anyway, it's not a huge speedup, but it helps me. Let me know if you
try the changes and run into bugs.
Thanks,
Manu
-------------- next part --------------
Index: soot/jimple/toolkits/typing/integer/TypeVariable.java
===================================================================
--- soot/jimple/toolkits/typing/integer/TypeVariable.java (revision 2275)
+++ soot/jimple/toolkits/typing/integer/TypeVariable.java (working copy)
@@ -32,6 +32,9 @@
import java.util.*;
import java.util.*;
+import manu.util.ArraySet;
+
+
/** Represents a type variable. **/
class TypeVariable implements Comparable
{
@@ -48,8 +51,8 @@
private TypeNode type;
- private List parents = Collections.unmodifiableList(new LinkedList());
- private List children = Collections.unmodifiableList(new LinkedList());
+ private ArraySet parents = new ArraySet();
+ private ArraySet children = new ArraySet();
public TypeVariable(int id, TypeResolver resolver)
{
@@ -182,18 +185,14 @@
// Merge parents
{
- Set set = new TreeSet(parents);
- set.addAll(var.parents);
- set.remove(this);
- parents = Collections.unmodifiableList(new LinkedList(set));
+ parents.addAll(var.parents);
+ parents.remove(this);
}
// Merge children
{
- Set set = new TreeSet(children);
- set.addAll(var.children);
- set.remove(this);
- children = Collections.unmodifiableList(new LinkedList(set));
+ children.addAll(var.children);
+ children.remove(this);
}
}
@@ -223,15 +222,11 @@
}
{
- Set set = new TreeSet(parents);
- set.add(var);
- parents = Collections.unmodifiableList(new LinkedList(set));
+ parents.add(var);
}
{
- Set set = new TreeSet(var.children);
- set.add(this);
- var.children = Collections.unmodifiableList(new LinkedList(set));
+ var.children.add(this);
}
}
@@ -246,15 +241,11 @@
TypeVariable var = variable.ecr();
{
- Set set = new TreeSet(parents);
- set.remove(var);
- parents = Collections.unmodifiableList(new LinkedList(set));
+ parents.remove(var);
}
{
- Set set = new TreeSet(var.children);
- set.remove(this);
- var.children = Collections.unmodifiableList(new LinkedList(set));
+ var.children.remove(this);
}
}
@@ -274,15 +265,11 @@
}
{
- Set set = new TreeSet(children);
- set.add(var);
- children = Collections.unmodifiableList(new LinkedList(set));
+ children.add(var);
}
{
- Set set = new TreeSet(var.parents);
- set.add(this);
- var.parents = Collections.unmodifiableList(new LinkedList(set));
+ var.parents.add(this);
}
}
@@ -297,15 +284,11 @@
TypeVariable var = variable.ecr();
{
- Set set = new TreeSet(children);
- set.remove(var);
- children = Collections.unmodifiableList(new LinkedList(set));
+ children.remove(var);
}
{
- Set set = new TreeSet(var.parents);
- set.remove(this);
- var.parents = Collections.unmodifiableList(new LinkedList(set));
+ var.parents.remove(this);
}
}
@@ -316,7 +299,7 @@
return ecr().parents();
}
- return parents;
+ return Collections.unmodifiableList(new ArrayList(parents));
}
public List children()
@@ -326,7 +309,7 @@
return ecr().children();
}
- return children;
+ return Collections.unmodifiableList(new ArrayList(children));
}
public TypeNode approx()
@@ -528,8 +511,8 @@
}
{
- Set set = new TreeSet(parents);
- parents = Collections.unmodifiableList(new LinkedList(set));
+// Set set = new TreeSet(parents);
+// parents = Collections.unmodifiableList(new LinkedList(set));
}
}
@@ -542,8 +525,8 @@
}
{
- Set set = new TreeSet(children);
- children = Collections.unmodifiableList(new LinkedList(set));
+// Set set = new TreeSet(children);
+// children = Collections.unmodifiableList(new LinkedList(set));
}
}
Index: soot/jimple/toolkits/typing/TypeVariable.java
===================================================================
--- soot/jimple/toolkits/typing/TypeVariable.java (revision 2275)
+++ soot/jimple/toolkits/typing/TypeVariable.java (working copy)
@@ -26,11 +26,20 @@
package soot.jimple.toolkits.typing;
-import soot.*;
-import soot.jimple.*;
-import soot.util.*;
-import java.util.*;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+import java.util.TreeSet;
+import soot.ArrayType;
+import soot.G;
+import soot.RefType;
+import manu.util.ArraySet;
+import soot.util.BitVector;
+
/** Represents a type variable. **/
class TypeVariable implements Comparable
{
@@ -49,8 +58,8 @@
private TypeVariable element;
private int depth;
- private List parents = Collections.unmodifiableList(new LinkedList());
- private List children = Collections.unmodifiableList(new LinkedList());
+ private ArraySet parents = new ArraySet();
+ private ArraySet children = new ArraySet();
private BitVector ancestors;
private BitVector indirectAncestors;
@@ -205,18 +214,14 @@
// Merge parents
{
- Set set = new TreeSet(parents);
- set.addAll(var.parents);
- set.remove(this);
- parents = Collections.unmodifiableList(new LinkedList(set));
+ parents.addAll(var.parents);
+ parents.remove(this);
}
// Merge children
{
- Set set = new TreeSet(children);
- set.addAll(var.children);
- set.remove(this);
- children = Collections.unmodifiableList(new LinkedList(set));
+ children.addAll(var.children);
+ children.remove(this);
}
}
@@ -349,15 +354,11 @@
}
{
- Set set = new TreeSet(parents);
- set.add(var);
- parents = Collections.unmodifiableList(new LinkedList(set));
+ parents.add(var);
}
{
- Set set = new TreeSet(var.children);
- set.add(this);
- var.children = Collections.unmodifiableList(new LinkedList(set));
+ var.children.add(this);
}
}
@@ -372,15 +373,11 @@
TypeVariable var = variable.ecr();
{
- Set set = new TreeSet(parents);
- set.remove(var);
- parents = Collections.unmodifiableList(new LinkedList(set));
+ parents.remove(var);
}
{
- Set set = new TreeSet(var.children);
- set.remove(this);
- var.children = Collections.unmodifiableList(new LinkedList(set));
+ var.children.remove(this);
}
}
@@ -400,15 +397,11 @@
}
{
- Set set = new TreeSet(children);
- set.add(var);
- children = Collections.unmodifiableList(new LinkedList(set));
+ children.add(var);
}
{
- Set set = new TreeSet(var.parents);
- set.add(this);
- var.parents = Collections.unmodifiableList(new LinkedList(set));
+ var.parents.add(this);
}
}
@@ -423,15 +416,11 @@
TypeVariable var = variable.ecr();
{
- Set set = new TreeSet(children);
- set.remove(var);
- children = Collections.unmodifiableList(new LinkedList(set));
+ children.remove(var);
}
{
- Set set = new TreeSet(var.parents);
- set.remove(this);
- var.parents = Collections.unmodifiableList(new LinkedList(set));
+ var.parents.remove(this);
}
}
@@ -487,7 +476,7 @@
return ecr().parents();
}
- return parents;
+ return Collections.unmodifiableList(new ArrayList(parents));
}
public List children()
@@ -497,7 +486,7 @@
return ecr().children();
}
- return children;
+ return Collections.unmodifiableList(new ArrayList(children));
}
public TypeNode approx()
@@ -826,8 +815,9 @@
}
{
- Set set = new TreeSet(parents);
- parents = Collections.unmodifiableList(new LinkedList(set));
+ // what is this supposed to do? eliminate duplicates?
+// Set set = new TreeSet(parents);
+// parents = Collections.unmodifiableList(new LinkedList(set));
}
}
@@ -840,8 +830,9 @@
}
{
- Set set = new TreeSet(children);
- children = Collections.unmodifiableList(new LinkedList(set));
+ // what is this supposed to do? eliminate duplicates?
+// Set set = new TreeSet(children);
+// children = Collections.unmodifiableList(new LinkedList(set));
}
}
Index: soot/toolkits/scalar/SmartLocalDefs.java
===================================================================
--- soot/toolkits/scalar/SmartLocalDefs.java (revision 2275)
+++ soot/toolkits/scalar/SmartLocalDefs.java (working copy)
@@ -53,12 +53,18 @@
localToDefs = new HashMap();
unitToMask = new HashMap();
+ final HashMap numbers = new HashMap();
+ ArrayList numberToUnit = new ArrayList();
+ int i = 0;
for( Iterator uIt = g.iterator(); uIt.hasNext(); ) {
final Unit u = (Unit) uIt.next();
Local l = localDef(u);
if( l == null ) continue;
- HashSet s = defsOf(l);
- s.add(u);
+ numberToUnit.add(u);
+ numbers.put(u, new Integer(i));
+ BitSet s = defsOf(l);
+ s.set(i);
+ i++;
}
if(Options.v().verbose())
@@ -75,7 +81,9 @@
G.v().out.println("[" + g.getBody().getMethod().getName() +
"] done unitToMask map..." );
- analysis = new LocalDefsAnalysis(graph);
+ Unit[] numberToUnitArr = (Unit[])numberToUnit.toArray(new Unit[numberToUnit.size()]);
+ numberToUnit = null;
+ analysis = new LocalDefsAnalysis(graph, numbers, numberToUnitArr);
answer = new HashMap();
for( Iterator uIt = graph.iterator(); uIt.hasNext(); ) {
@@ -84,12 +92,12 @@
final ValueBox vb = (ValueBox) vbIt.next();
Value v = vb.getValue();
if( !(v instanceof Local) ) continue;
- HashSet analysisResult = (HashSet) analysis.getFlowBefore(u);
+ BitSet analysisResult = (BitSet) analysis.getFlowBefore(u);
ArrayList al = new ArrayList();
- for( Iterator unitIt = defsOf((Local)v).iterator(); unitIt.hasNext(); ) {
- final Unit unit = (Unit) unitIt.next();
- if(analysisResult.contains(unit)) al.add(unit);
- }
+ BitSet defsOf = defsOf((Local)v);
+ for(int j=defsOf.nextSetBit(0); j>=0; j=defsOf.nextSetBit(j+1)) {
+ if(analysisResult.get(j)) al.add(numberToUnitArr[j]);
+ }
answer.put(new Cons(u, v), al);
}
}
@@ -109,63 +117,73 @@
if( !(v instanceof Local) ) return null;
return (Local) v;
}
- private HashSet defsOf( Local l ) {
- HashSet ret = (HashSet)localToDefs.get(l);
- if( ret == null ) localToDefs.put( l, ret = new HashSet() );
+ private BitSet defsOf( Local l ) {
+ BitSet ret = (BitSet)localToDefs.get(l);
+ if( ret == null ) localToDefs.put( l, ret = new BitSet() );
return ret;
}
class LocalDefsAnalysis extends ForwardFlowAnalysis {
- LocalDefsAnalysis(UnitGraph g) {
+
+ final Map unitToNumber;
+
+ final Unit[] numberToUnit;
+
+ LocalDefsAnalysis(UnitGraph g, Map numbers, Unit[] numberToUnit) {
super(g);
+ this.unitToNumber = numbers;
+ this.numberToUnit = numberToUnit;
doAnalysis();
}
protected void merge(Object inoutO, Object inO) {
- HashSet inout = (HashSet) inoutO;
- HashSet in = (HashSet) inO;
+ BitSet inout = (BitSet) inoutO;
+ BitSet in = (BitSet) inO;
- inout.addAll(in);
+ inout.or(in);
}
protected void merge(Object in1, Object in2, Object out) {
- HashSet inSet1 = (HashSet) in1;
- HashSet inSet2 = (HashSet) in2;
- HashSet outSet = (HashSet) out;
+ BitSet inSet1 = (BitSet) in1;
+ BitSet inSet2 = (BitSet) in2;
+ BitSet outSet = (BitSet) out;
outSet.clear();
- outSet.addAll(inSet1);
- outSet.addAll(inSet2);
+ outSet.or(inSet1);
+ outSet.or(inSet2);
}
protected void flowThrough(Object inValue, Object unit, Object outValue) {
Unit u = (Unit) unit;
- HashSet in = (HashSet) inValue;
- HashSet out = (HashSet) outValue;
+ BitSet in = (BitSet) inValue;
+ BitSet out = (BitSet) outValue;
out.clear();
Set mask = (Set) unitToMask.get(u);
- for( Iterator inUIt = in.iterator(); inUIt.hasNext(); ) {
- final Unit inU = (Unit) inUIt.next();
- if( mask.contains(localDef(inU)) ) out.add(inU);
+ for(int i=in.nextSetBit(0); i>=0; i=in.nextSetBit(i+1)) {
+ // operate on index i here
+ final Unit inU = numberToUnit[i];
+ if( mask.contains(localDef(inU)) ) out.set(i);
}
+
Local l = localDef(u);
if( l != null ) {
- out.removeAll(defsOf(l));
- if(mask.contains(localDef(u))) out.add(u);
+ BitSet defsOf = defsOf(l);
+ out.andNot(defsOf);
+ if(mask.contains(localDef(u))) out.set(((Integer)unitToNumber.get(u)).intValue());
}
}
protected void copy(Object source, Object dest) {
- HashSet sourceSet = (HashSet) source;
- HashSet destSet = (HashSet) dest;
+ BitSet sourceSet = (BitSet) source;
+ BitSet destSet = (BitSet) dest;
destSet.clear();
- destSet.addAll(sourceSet);
+ destSet.or(sourceSet);
}
protected Object newInitialFlow() {
- return new HashSet();
+ return new BitSet();
}
protected Object entryInitialFlow() {
- return new HashSet();
+ return new BitSet();
}
}
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ArraySet.java
Type: text/x-java
Size: 3967 bytes
Desc: not available
Url : http://mailman.CS.McGill.CA/pipermail/soot-list/attachments/20060130/57d2dece/ArraySet.bin
More information about the Soot-list
mailing list