[Soot-list] Bug in shimple transformation ?

[Jonas.Lundberg at msi.vxu.se]

Hi again,

First of all I would like to thank you for the time and effort 
spent on improving Shimple. I have had a quick glance at Nightly 
build 2240. It seems to solve the problem with missing phi-
functions for certain multi-valued references. At least for the 
three examples that I pointed out in my last mail.

However, it seems like your code changes have introduced a 
performance bottle-neck. The time spent on constructing the 
Shimple bodies has increased considerably.

I have used a profiling tool and it reports the following when 
applied on a whole program ananlysis of javac:

- 88% of the method body construction time is spent on Shimple   
construction(and the rest on Jimple)

- 91% of the time is spent on about thousand calls to the method 
  soot.toolkits.graph.MHGDominatorsAnalysis.doAnalysis

- Most of this time is spent on a very large number of   
operations on instances of the class
       soot.toolkits.scalar.ArraySparseSet

- For example, 46,0% is spent on 4.358.481 calls to
       soot.toolkits.scalar.ArraySparseSet.contains
       
I guess that you have added some code that, for a certain input 
methods, drastically changes the time complexity of the SSA 
construction algorithm. This can be noted just by looking at a 
print-out of methods as they are processed. It seems to stop 
(and almost die) when certain methods are processed. This 
happens just a few times during a whole program analysis. A 
rough estimate is that 90% of the time is spent on these few 
methods. 

Here is a list of a few "problematic" methods 
<java.lang.CharacterDataLatin1: void <clinit>()>
<java.util.LinkedHashMap: java.lang.Objectget(java.lang.Object)>
<java.io.FileReader: void <init>(java.lang.String)>
<java.util.Hashtable: java.lang.Object get(java.lang.Object)>
Notice, none of the methods are large in terms of statements.

Finally, I'm not using Soot as command line tool and maybe I do 
something wrong on my way. I use Soot from within a Java program 
and I need to get access to all Shimple method bodies of a whole 
program. This is my approach:

I use Options.v() to setup  the analysis
   Options.v().set_soot_classpath( ...);
   ...
   Options.v().set_full_resolver(true);
   Options.v().set_whole_program(true);  		                       
//Options.v().set_whole_shimple(true);
   Scene.v().loadNecessaryClasses();
	
Then I ask Scene.v() for all concrete SootMethod and do the 
following for each SootMethod sM

   Body body = sM.retrieveActiveBody();//Returns a JimpleBody
   ShimpleBody sBody = Shimple.v().newBody(body);
			
I have a few questions regarding this approach:

1. I always get a JimpleBody when using retrieveActiveBody(),    
even in cases when I use the options set_whole_shimple(true).
What is the point of using set_whole_shimple if not to get 
Shimple bodies?

2. I first create a JimpleBody and after that, by  
Shimple.v().newBody, I create a ShimpleBody. Is this a stupid 
approach or is it the way Shimple bodies are created in any 
case?
   
Any help on handling the performance bottleneck, or comment on 
the questions raised would be appreciated.

Regards - Jonas


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.CS.McGill.CA/pipermail/soot-list/attachments/20051118/4878ee80/attachment.htm