[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
EdgesOutOf
Hi,
I'm currently implementing a whole-program analysis with Soot. I have a
registered SceneTransformer with an internalTransform() method looping
over reachable methods, and looping over statements.
The code of this analysis is attached, and a relevant (verbose but
simple, eh, it's java) skeleton is presented below.
I wonder why the edgesOutOf(Unit) method always returns an empty
iterator. When I iterate over the callees of a method, obtained through
edgesOutOf(SootMethod), I see the right methods called, an even the
srcUnit() and srcStmt() are right
It looks juste like if the edgesOutOf(Unit) is broken, but its source
code seems right. Or maybe am I missing something evident ?
Any help would be greatly appreciated.
-G
protected void internalTransform(String phaseName, Map options)
{
CallGraph cg=Scene.v().getCallGraph();
SootMethod mainMethod=
Scene.v().getMainClass().getMethodByName("main");
worklist.add(mainMethod)
while (worklist.size()>0)
{
if(!theMethod.hasActiveBody()) continue;
Body body=theMethod.getActiveBody();
Chain units = body.getUnits();
while(stmtIt.hasNext())
{
Stmt theStmt = (Stmt) stmtIt.next();
System.out.println(theStmt+" ("+theStmt.getClass()+")");
Iterator zobIt=cg.edgesOutOf(theStmt);
while(zobIt.hasNext())
{
SootMethod callee=((Edge)zobIt.next()).getTgt().method();
System.out.println("+calls (stmt) (CG): "+callee);
}
zobIt=cg.edgesOutOf(theMethod);
while(zobIt.hasNext())
{
Edge e=(Edge)zobIt.next();
SootMethod callee=e.getTgt().method(); g
System.out.println("+calls (method) (CG): "+callee);
System.out.println("+ srcUnit: "+e.srcUnit());
System.out.println("+ srcStmt: "+e.srcStmt());
}
}
}
}
--
Guillaume Salagnac -- EtK/WarpZone -- 06.68.37.60.78
Equipe "Systèmes Temporisés et Hybrides." Verimag. Grenoble. France.
Mangez un castor, vous sauverez un arbre.// FreshnessAnalysis.java - Guillaume Salagnac - lun 13 sep 2004, 9:53
// Time-stamp: "2004-09-20 16:20:50 salagnac"
import java.io.*;
import java.util.*;
import java.lang.*;
import soot.*;
import soot.jimple.*;
import soot.shimple.*;
import soot.jimple.toolkits.callgraph.*;
import soot.tagkit.*;
import soot.toolkits.graph.*;
import soot.toolkits.scalar.*;
import soot.tools.*;
import soot.util.*;
// implémentation d'un algo inspiré de [GS00] (David Gay and Bjarne
// Steensgaard. Fast Escape Analysis and Stack Allocation for
// Object-Based Programs, CC'2000)
class FreshnessAnalysis extends SceneTransformer
{
private static FreshnessAnalysis instance = new FreshnessAnalysis();
private FreshnessAnalysis() {}
public static FreshnessAnalysis v() { return instance; }
// les deux éléments constants du treillis F
public static final String TOP="TOP";
public static final String BOTTOM="BOTTOM";
// la borne sup du treillis
Object upperBound(Object f1,Object f2)
{
Object r;
if(f1 == null || f2 == null)
throw new NullPointerException("je ne mange pas de ce pain-là");
if(f1.equals(f2)) r=f1;
else if(f1.equals(BOTTOM)) r=f2;
else if(f2.equals(BOTTOM)) r=f1;
else r=TOP;
//System.out.print("upperBound("+f1+","+f2+")="+r);
return r;
}
// met à jour la valeur map(dest) := upperBound( map(dest), constraint)
//
// retourne true si la valeur a changé dans l'opération, false sinon
boolean update(HashMap map,Object dest,Object constraint)
{
boolean changed=false;
// programmation défensive
if(!map.containsKey(dest))
throw new RuntimeException(mapName(map)+" doesn't contain "+dest);
Object bound=upperBound(map.get(dest),constraint);
if(!map.put(dest,bound).equals(bound))
{
System.out.println(mapName(map)+": "+dest+" -> "+bound);
changed=true;
}
return changed;
}
HashMap mfresh;
HashMap fresh;
HashMap loop;
HashMap escaped;
HashMap returned;
String mapName(HashMap map)
{
if(map==mfresh) return "MFRESH";
else if(map==fresh) return "FRESH";
else if(map==loop) return "LOOP";
else if(map==escaped) return "ESCAPED";
else if(map==returned) return "RETURNED";
throw new RuntimeException("Unknown map:"+map);
}
protected void internalTransform(String phaseName, Map options)
{
System.out.println("======================================== Start freshness analysis");
Iterator clIt=Scene.v().getApplicationClasses().iterator();
System.out.println("Application classes:\n");
while(clIt.hasNext())
{
SootClass cl=(SootClass)clIt.next();
System.out.println(" "+cl);
Iterator mIt=cl.getMethods().iterator();
while(mIt.hasNext())
{
SootMethod m=(SootMethod)mIt.next();
System.out.println(" "+m);
addToWorklist(m);
}
}
CallGraph cg=Scene.v().getCallGraph();
if (!Scene.v().getMainClass().
declaresMethod("void main(java.lang.String[])"))
throw new RuntimeException("couldn't find main() in main Class");
SootMethod mainMethod=Scene.v().getMainClass().getMethodByName("main");
addToWorklist(mainMethod);
mfresh=new HashMap();
fresh=new HashMap();
loop=new HashMap();
escaped=new HashMap();
returned=new HashMap();
while (worklist.size()>0)
{
SootMethod theMethod = (SootMethod) worklist.remove(0);
System.out.println("========== "+theMethod);
if(!mfresh.containsKey(theMethod))
{
mfresh.put(theMethod,BOTTOM);
System.out.println("MFRESH: added "+theMethod.getName()+" ("+BOTTOM+")");
addCallersAndCallees(theMethod,true);
}
if(!theMethod.hasActiveBody()) continue;
Body body=theMethod.getActiveBody();
Chain locals = body.getLocals();
Iterator lIt =locals.iterator();
while(lIt.hasNext())
{
Local l=(Local)lIt.next();
if(l.getType() instanceof RefLikeType)
{
if(!fresh.containsKey(l))
{
fresh.put(l,BOTTOM);
escaped.put(l,BOTTOM);
loop.put(l,BOTTOM);
returned.put(l,BOTTOM);
System.out.println("FRESH: new local "+l+" ("+l.getType()+")");
addToWorklist(theMethod);
}
}
}
/*******************/
Chain units = body.getUnits();
System.out.println(units.size()+" instructions");
Iterator stmtIt = units.iterator();
while(stmtIt.hasNext())
{
Stmt theStmt = (Stmt) stmtIt.next();
System.out.println(theStmt+" ("+theStmt.getClass()+")");
Iterator zobIt=cg.edgesOutOf(theStmt);
while(zobIt.hasNext())
{
SootMethod callee=((Edge)zobIt.next()).getTgt().method(); // callee == g
System.out.println("+calls (stmt) (CG): "+callee);
}
zobIt=cg.edgesOutOf(theMethod);
while(zobIt.hasNext())
{
Edge e=(Edge)zobIt.next();
SootMethod callee=e.getTgt().method(); // callee == g
System.out.println("+calls (method) (CG): "+callee);
System.out.println("+ srcUnit: "+e.srcUnit());
System.out.println("+ srcStmt: "+e.srcStmt());
}
if( theStmt instanceof DefinitionStmt)
{
Value lhs=((DefinitionStmt)theStmt).getLeftOp();
Value rhs=((DefinitionStmt)theStmt).getRightOp();
//System.out.println(" lhs="+lhs+" ("+lhs.getClass()+")");
//System.out.println(" rhs="+rhs+" ("+rhs.getClass()+")");
if(lhs instanceof Local && lhs.getType() instanceof RefLikeType)
{
if(rhs instanceof NewExpr) // on ne prend pas les NewArrayExpr ([GS98] sec2.1, GS00 ??)
{
System.out.println(" Allocation site:"+theStmt);
if(update(fresh,lhs,rhs.getType()))
addToWorklist(theMethod);
}
else if ( rhs instanceof PhiExpr )
{
if(update(fresh,lhs,TOP))
addToWorklist(theMethod);
// itérer sur les vi ([GS00]fig.2 et fig.3)
Iterator viIt=((PhiExpr)rhs).getValues().iterator();
while(viIt.hasNext())
{
Value vi=(Value)viIt.next();
if(!( vi instanceof Local))
continue;
if( update(loop,vi,TOP)
|| update(escaped,vi,escaped.get(lhs))
|| update(returned,vi,returned.get(lhs)) )
addToWorklist(theMethod);
}
}
else if( rhs instanceof Local ) // v0 = v1
{
if(update(escaped,rhs,escaped.get(lhs))
|| update(returned,rhs,returned.get(lhs))
|| update(loop,rhs,loop.get(lhs))
|| update(fresh,lhs,TOP))
addToWorklist(theMethod);
}
else if( rhs instanceof Ref )
{
if(update(fresh,lhs,TOP))
addToWorklist(theMethod);
}
else if( rhs instanceof InvokeExpr) // [GS00] fig.2, dernier cas. v0=v1.m(v2,...vn)
{
// méthodes *potentiellement* appelées
// (grâce à la surcharge) selon le CG
System.out.println("InvokeExpr !\n");
Iterator tempIt=cg.edgesOutOf(theMethod);
while(tempIt.hasNext())
{
SootMethod callee=((Edge)tempIt.next()).getTgt().method(); // callee == g
System.out.println(" calls (method) (CG): "+callee);
}
Iterator mIt=cg.edgesOutOf(theStmt); // [GS00]: forall g in methods-invoked(v1.m)
while(mIt.hasNext())
{
SootMethod callee=((Edge)mIt.next()).getTgt().method(); // callee == g
System.out.println(" calls (stmt) (CG): "+callee);
Body cBody=callee.getActiveBody();
for(int i=0;i<callee.getParameterCount();i++)
{
System.out.println(" parameter "+i+": "+cBody.getParameterLocal(i));
}
// mfresh(g) <= vfresh(vo)
if(!mfresh.containsKey(callee))
{
mfresh.put(callee,BOTTOM);
System.out.println("MFRESH: (new method) "+callee+" -> "+BOTTOM);
addToWorklist(callee);
}
if(update(fresh,lhs,mfresh.get(callee)))
if(Scene.v().getApplicationClasses().contains(callee.getDeclaringClass()))
addToWorklist(callee);
}
}
}// lhs intanceof Local
else if( lhs instanceof Ref )
{
if(rhs instanceof Local && rhs.getType() instanceof RefLikeType)
if(update(escaped,rhs,TOP))
addToWorklist(theMethod);
}// lhs intanceof Ref
}//theStmt instanceof DefinitionStmt
else if(theStmt instanceof ReturnStmt)
{
Value op=((ReturnStmt)theStmt).getOp();
if(op instanceof Local && op.getType() instanceof RefLikeType)
{
if( update(returned,op,TOP)
|| update(mfresh,theMethod,fresh.get(op))
|| update(mfresh,theMethod,escaped.get(op)) )
addCallersAndCallees(theMethod,true);
}
}// theStmt instanceof ReturnStmt
else if(theStmt instanceof ThrowStmt)
{
Value op=((ReturnStmt)theStmt).getOp();
if(op instanceof Local && op.getType() instanceof RefLikeType)
if( update(escaped,op,TOP) )
addToWorklist(theMethod);
}
}//stmtIt.hasNext()
}// worklist.size()>0
System.out.println("==================== Results");
Iterator mIt=reachable_methods.iterator();
while(mIt.hasNext())
{
SootMethod m=(SootMethod)mIt.next();
System.out.println("==========");
System.out.println(m+" -> "+mfresh.get(m));
if(!m.hasActiveBody()) continue;
Body body=m.getActiveBody();
Chain locals = body.getLocals();
Iterator lIt =locals.iterator();
while(lIt.hasNext())
{
Local l=(Local)lIt.next();
if(!( l.getType() instanceof RefLikeType))
continue;
boolean stackable=
!fresh.get(l).equals(BOTTOM) // *is* fresh
&& !fresh.get(l).equals(TOP) // *is* fresh
&& loop.get(l).equals(BOTTOM) // *is not* defined in a loop
&& escaped.get(l).equals(BOTTOM) // *does not* escape
&& returned.get(l).equals(BOTTOM) // *is not* returned
;
//boolean stackable=false;
System.out.println(l+"\t-> "
+"\t loop:"+loop.get(l)
+"\t returned:"+returned.get(l)
+"\t escaped:"+escaped.get(l)
+"\t fresh:"+fresh.get(l)
+( stackable ? " ==> STACKABLE" : "")
);
}
}
System.out.println("======================================= Finished freshness analysis");
}
// ---------------------------------------------------------
// worklist (which is basically a queue) that stores methods whose
// bodies have to be processed.
private ArrayList worklist = new ArrayList();
// ----------------------------------------------------------
// The set of all methods already seen .
private HashSet reachable_methods = new HashSet();
// --------------------------------------------------------------
// a helper method for adding a newly-discovered reachable method
// to the end of the worklist. this schedules the method for
// processing in the future.
private void addToWorklist(SootMethod m)
{
// debugging print
//System.out.println("addToWorklist("+m+")");
//if (reachable_methods.contains(m))
// return; // we only add methods that haven't been discovered yet
if(!worklist.contains(m))
{
worklist.add(m); // add at the end of the worklist
//System.out.println("added to worklist: "+m);
}
// add to the set of reachable methods
reachable_methods.add(m);
}
private void addCallersAndCallees(SootMethod m,boolean onlyFromApp)
{
System.out.println("addCallersAndCallees("+m+")");
CallGraph cg=Scene.v().getCallGraph();
Iterator mIt=cg.edgesOutOf(m);
while(mIt.hasNext())
{
SootMethod callee=((Edge)mIt.next()).getTgt().method();
if(!onlyFromApp || Scene.v().getApplicationClasses().contains(callee.getDeclaringClass()))
{
System.out.println("-calls (CG): "+callee);
addToWorklist(callee);
}
}
mIt=cg.edgesInto(m);
while(mIt.hasNext())
{
SootMethod caller=((Edge)mIt.next()).getTgt().method();
if(!onlyFromApp || Scene.v().getApplicationClasses().contains(caller.getDeclaringClass()))
{
System.out.println("-called by (CG): "+caller);
addToWorklist(caller);
}
}
}
}
/*
{
// méthode appelée, selon le source.
SootMethod callee=((InvokeExpr)rhs).getMethod();
System.out.println(" calls (sig): "+callee);
if(!mfresh.containsKey(callee))
{
mfresh.put(callee,BOTTOM);
System.out.println("MFRESH: (new method) "+callee+" -> "+BOTTOM);
//addCallersAndCallees(theMethod,true);
}
if(Scene.v().getApplicationClasses().contains(callee.getDeclaringClass()))
{
addToWorklist(callee);
System.out.println(" added to worklist: "+callee);
}
if(update(fresh,lhs,mfresh.get(callee))) // mfresh(g) <= vfresh(vo)
addCallersAndCallees(theMethod,true);
}
*/
// Main.java - Guillaume Salagnac - lun 13 sep 2004, 9:51
// Time-stamp: "2004-09-20 11:00:08 salagnac"
// un premier essai d'implémentation de la freshness analysis telle
// que présentée dans GS00
import soot.*;
import soot.jimple.*;
import soot.tagkit.LineNumberTag;
import soot.tagkit.Tag;
import soot.toolkits.scalar.*;
import soot.toolkits.graph.CompleteUnitGraph;
import soot.util.*;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.*;
public class Main
{
public static void main(String[] args)
{
if(args.length == 0)
{
System.out.println("Syntax: Main [soot options] ClassToAnalyze");
System.exit(0);
}
String[] optsDefault = {"-ws",
"-f","S",
"-p","jb","use-original-names:true",
"-p","cg","verbose:true"};
String[] opts= new String[optsDefault.length + args.length];
for(int i=0;i<optsDefault.length;i++)
opts[i]=optsDefault[i];
for(int i=0;i<args.length;i++)
opts[i+optsDefault.length]=args[i];
PackManager.v().getPack("wstp").add(new Transform("wstp.freshness",
FreshnessAnalysis.v()));
soot.Main.main(opts);
}
}