[Soot-list] Stack overflow when generating call graph

[me133 at columbia.edu]

Greetings!

First I'd like to say that Soot is a wonderful analysis tool and has  
saved us a great deal of time and effort.  We are using Polyglot to  
parse the Java source files for Rhino, an open source JavaScript  
interpreter/compiler.  We then use Soot to generate a complete call  
graph, i.e., we generate a call graph that considers all methods in  
the program, not just the Main entry point:

<snip>

Options.v().set_src_prec(Options.src_prec_java);
Options.v().set_whole_program(true);
Options.v().set_time(true);
Options.v().set_verbose(true);
Options.v().set_debug(true);
Options.v().set_debug_resolver(true);
Scene.v().loadBasicClasses();

for <all classes in Rhino>
     SootClass cl = Scene.v().loadClassAndSupport(classname);
     cl.setApplicationClass();

Scene.v().loadNecessaryClasses();
String thePhaseName = "cg";
HashMap theOptions = new HashMap();
theOptions.put("enabled", "true");
System.out.println("Setting options...");
SceneTransformer sctform;

... disabled a bunch of cg phases (see below) ...

PhaseOptions.v().setPhaseOption("cg", "implicit-entry:false");
PhaseOptions.v().setPhaseOption("cg", "verbose:true");
PhaseOptions.v().setPhaseOption("cg", "jdkver:4");
PhaseOptions.v().setPhaseOption("cg", "all-reachable:true");

if (pointsTo)
{
	//PhaseOptions.v().setPhaseOption("cg", "set-impl:hash");
	theOptions.put("set-impl", "hash");
	//theOptions.put("set-impl", "bit");

	// Try turning on to see if we avoid exception_stack_overflow
	//theOptions.put("on-fly-cg", "true");

	//theOptions.put("propagator", "worklist");
	theOptions.put("propagator", "alias");
	theOptions.put("dump-html", "true");
	sctform = SparkTransformer.v();
}
else
{
	sctform = CHATransformer.v();
}

sctform.transform(thePhaseName, theOptions);

System.out.println("Retrieving call graph...");
CallGraph cg = Scene.v().getCallGraph();

<snip>

We include all methods in the cg, not just the reachable ones, because  
we are creating a call dependency graph for our analysis.

The problem is that midway during cg creation Java throws a stack  
overflow exception because it runs out of memory (not because of  
infinite recursion).
Both CHA and Spark cause the exception to be thrown (although  
sometimes CHA works).

I'm using -Xms512m and -Xmx1512m, the machine has 2GB RAM, and Rhino  
is about 33 KLOCs.  I ran jmap and it looks like Soot is creating  
millions of hash table entries and a huge number of Polyglot edges.  I  
ran jstat and it appears that Soot eventually exhausts all the memory  
on the machine.

I tried disabling as much of the analysis phases as possible:

<snip>

PhaseOptions.v().setPhaseOption("jb.ne", "enabled:false");
PhaseOptions.v().setPhaseOption("jj.ne", "enabled:false");
PhaseOptions.v().setPhaseOption("jb.uce", "enabled:false");
PhaseOptions.v().setPhaseOption("jj.uce", "enabled:false");
PhaseOptions.v().setPhaseOption("jb.dae", "enabled:false");
PhaseOptions.v().setPhaseOption("jj.dae", "enabled:false");
PhaseOptions.v().setPhaseOption("jb.ule", "enabled:false");
PhaseOptions.v().setPhaseOption("jj.ule", "enabled:false");
PhaseOptions.v().setPhaseOption("jb.cp-ule", "enabled:false");
PhaseOptions.v().setPhaseOption("jj.cp-ule", "enabled:false");
PhaseOptions.v().setPhaseOption("jop", "enabled:false");
PhaseOptions.v().setPhaseOption("wjop", "enabled:false");

<snip>

This helps but only serves to postpone the stack overflow.

1. Is there any way to config cg so that it doesn't create edges/nodes  
for non-application program elements (e.g., system libraries)?  Based  
on a previous post, my guess is no, since doing whole program analysis  
always pulls in the world for completenes.  The problem is that the  
world is fairly large.

2. Is there any other way/flag/setting/option to config cg to optimize  
memory usage?

3. Otherwise, can a Soot developer give me some suggestions on how I  
can modify the cg code?  For example, if we call into a system library  
but there is never a call back into the application classes, we could  
prune the system library dag.

Thank you so much for helping me out with this!  And thanks again for  
the great tool!

Cheers,

Marc Eaddy