[Soot-list] Spark's TypeManager patch

[Hamid A. Toussi]

Hello all,

This patch makes TypeManager of Spark significantly faster specially
in cases that on-fly-cg is turned off. TypeManager is responsible for
making type masks before doing points-to sets propagation.

Below is an overview:
Making TypeManager faster by making type masks during a
depth-first-traversal on the class hierarchy. First, type-masks of the
leaves of Class Hierarchy are created and then the type mask of each
type T is obtained by ORing type maks of T’s sub-types and setting the
bit-numbers associated with Allocation Nodes of type T. Type-mask
of each interface is achieved by ORing type-masks of its top-level
concrete implementers. In fact, Reference types are visited in
reversed-topological-order.

A patch is attached that can be applied to
soot/jimple/spark/internal/TypeManager.java.
A Java class is also attached which can be used for testing this patch
as follows:

        Date startFTM = new Date();
        FastTypeManager ftm = new FastTypeManager(pag);
        if (!opts.ignore_types())
        	ftm.setFastHierarchy(Scene.v().getFastHierarchy());
        ftm.makeTypeMask();
        Date endFTM = new Date();
        reportTime("Fast Type masks", startFTM, endFTM);

        Set<AllocNode> set = new HashSet<AllocNode>();
        for( Iterator tIt = Scene.v().getTypeNumberer().iterator();
tIt.hasNext(); ) {
            final Type t = (Type) tIt.next();
            if( !(t instanceof RefLikeType) ) continue;
            if( t instanceof AnySubType ) continue;
            if( FastTypeManager.isUnresolved(t) ) continue;
            BitVector orig = pag.getTypeManager().get(t);
            BitVector nmask = ftm.get(t);
            if (orig.equals(nmask)) continue;
            BitVector temp = new BitVector(nmask);
            temp.xor(orig);
            for (BitSetIterator it = temp.iterator(); it.hasNext(); ) {
            	int n = it.next();
            	AllocNode an = (AllocNode)pag.getAllocNodeNumberer().get(n);
            	set.add(an);
            }
        }
        for (AllocNode an : set) G.v().out.println(an);
        for( Iterator tIt = Scene.v().getTypeNumberer().iterator();
tIt.hasNext(); ) {
            final Type t = (Type) tIt.next();
            if( !(t instanceof RefLikeType) ) continue;
            if( t instanceof AnySubType ) continue;
            if( FastTypeManager.isUnresolved(t) ) continue;
            BitVector orig = pag.getTypeManager().get(t);
            BitVector nmask = ftm.get(t);
            for (AllocNode an : set) {
            	if (orig.get(an.getNumber()) && !nmask.get(an.getNumber())) {
            		G.v().out.print(t +" mask should contain "+an+": ");
            		if (!(t instanceof RefType)) throw new RuntimeException();
            		SootClass sc = ((RefType)t).getSootClass();
            		if (!sc.isInterface()) G.v().out.print(" not interface");
            		G.v().out.println(Scene.v().getFastHierarchy().
            				getAllImplementersOfInterface(sc).size());
            	}
            	if (!orig.get(an.getNumber()) && nmask.get(an.getNumber())) {
            		G.v().out.println(t +" shouldn't contain "+an);
            	}
            }
        }

Testing should be done before applying the patch using the original TypeManager.

Thanks,
Hamid
-------------- next part --------------
A non-text attachment was scrubbed...
Name: FastTypeManager.java
Type: text/x-java
Size: 8595 bytes
Desc: not available
Url : http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20120107/10e34d92/attachment-0002.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ftm.patch
Type: text/x-patch
Size: 9367 bytes
Desc: not available
Url : http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20120107/10e34d92/attachment-0003.bin