Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 2007 Patrick Lam
   * Copyright (C) 2007 Eric Bodden
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Lesser General Public
   * License as published by the Free Software Foundation; either
   * version 2.1 of the License, or (at your option) any later version.
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * Lesser General Public License for more details.
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  * Boston, MA 02111-1307, USA.
 package soot.jimple.toolkits.pointer;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import soot.Local;
 import soot.Scene;
 import soot.Unit;
 import soot.Value;
 import soot.ValueBox;
LocalMustAliasAnalysis attempts to determine if two local variables (at two potentially different program points) must point to the same object. The underlying abstraction is based on global value numbering. See also StrongLocalMustAliasAnalysis for an analysis that soundly treats redefinitions within loops. See Sable TR 2007-8 for details. P.S. The idea behind this analysis and the way it assigns numbers is very similar to what is described in the paper: Lapkowski, C. and Hendren, L. J. 1996. Extended SSA numbering: introducing SSA properties to languages with multi-level pointers. In Proceedings of the 1996 Conference of the Centre For Advanced Studies on Collaborative Research (Toronto, Ontario, Canada, November 12 - 14, 1996). M. Bauer, K. Bennet, M. Gentleman, H. Johnson, K. Lyons, and J. Slonim, Eds. IBM Centre for Advanced Studies Conference. IBM Press, 23. Only major differences: Here we only use primary numbers, no secondary numbers. Further, we use the call graph to determine fields that are not written to in the transitive closure of this method's execution. A third difference is that we assign fixed values to soot.jimple.IdentityRefs, because those never change during one execution.

Patrick Lam
Eric Bodden
See also:
 	public static final String UNKNOWN_LABEL = "UNKNOWN";
 	protected static final Object UNKNOWN = new Object() {
     	public String toString() { return ; }
     protected static final Object NOTHING = new Object() {
     	public String toString() { return "NOTHING"; }
The set of all local variables and field references that we track. This set contains objects of type soot.Local and, if tryTrackFieldAssignments is enabled, it may also contain soot.EquivalentValues of soot.jimple.FieldRefs. If so, these field references are to be tracked on the same way as soot.Locals are.
     protected Set<ValuelocalsAndFieldRefs;

maps from right-hand side expressions (non-locals) to value numbers
     protected transient Map<Value,IntegerrhsToNumber;
maps from a merge point (a unit) and a value to the unique value number of that value at this point
    protected transient Map<Unit,Map<Value,Integer>> mergePointToValueToNumber;

the next value number
    protected int nextNumber = 1;

the containing method
	protected SootMethod container;
Creates a new LocalMustAliasAnalysis tracking local variables.
    public LocalMustAliasAnalysis(UnitGraph g) {

Creates a new LocalMustAliasAnalysis. If tryTrackFieldAssignments, we run an interprocedural side-effects analysis to determine which fields are (transitively) written to by this method. All fields which that are not written to are tracked just as local variables. This semantics is sound for single-threaded programs.
	public LocalMustAliasAnalysis(UnitGraph gboolean tryTrackFieldAssignments) {
        this. = g.getBody().getMethod();
        this. = new HashSet<Value>(); 
        //add all locals
        for (Local l : (Collection<Local>) g.getBody().getLocals()) {
            if (l.getType() instanceof RefLikeType)
        if(tryTrackFieldAssignments) {
       	this. = new HashMap<ValueInteger>();
        this. = new HashMap<Unit,Map<Value,Integer>>();
        //not needed any more
        this. = null;
        this. = null;

Computes the set of soot.EquivalentValues of all field references that are used in this method but not set by the method or any method transitively called by this method.
    private Set<ValuetrackableFields() {
    	Set<ValueusedFieldRefs = new HashSet<Value>();
        //add all field references that are in use boxes
        for (Unit unit : this.) {
			Stmt s = (Stmtunit;
			List<ValueBoxuseBoxes = s.getUseBoxes();
			for (ValueBox useBox : useBoxes) {
				Value val = useBox.getValue();
				if(val instanceof FieldRef) {
					FieldRef fieldRef = (FieldRefval;
					if(fieldRef.getType() instanceof RefLikeType)
						usedFieldRefs.add(new EquivalentValue(fieldRef));						
        //prune all fields that are written to
        if(!usedFieldRefs.isEmpty()) {
	    	if(!Scene.v().hasCallGraph()) {
	    		throw new IllegalStateException("No call graph found!");
			CallGraph cg = Scene.v().getCallGraph();
			for (Iterator<MethodOrMethodContextiterator = reachableMethods.listener(); iterator.hasNext();) {
				SootMethod m = (;
				if(m.hasActiveBody() &&
				//exclude static initializer of same class (assume that it has already been executed)
					for (Unit u : m.getActiveBody().getUnits()) {
						List<ValueBoxdefBoxes = u.getDefBoxes();
						for (ValueBox defBox : defBoxes) {
							Value value = defBox.getValue();
							if(value instanceof FieldRef) {
								usedFieldRefs.remove(new EquivalentValue(value));
		return usedFieldRefs;
	protected void merge(Unit succUnitHashMap<Value,ObjectinMap1HashMap<Value,ObjectinMap2HashMap<Value,ObjectoutMap)
        for (Value l : ) {
            Object i1 = inMap1.get(l), i2 = inMap2.get(l);
            if (i1.equals(i2)) 
            else if (i1 == )
            else if (i2 == )
            else {
                /* Merging two different values is tricky...
                 * A naive approach would be to assign UNKNOWN. However, that would lead to imprecision in the following case:
                 * x = null;
                 * if(p) x = new X();
                 * y = x;
                 * z = x;
                 * Even though it is obvious that after this block y and z are aliased, both would be UNKNOWN :-(
                 * Hence, when merging the numbers for the two branches (null, new X()), we assign a value number that is unique
                 * to that merge location. Consequently, both y and z is assigned that same number!
                 * In the following it is important that we use an IdentityHashSet because we want the number to be unique to the
                 * location. Using a normal HashSet would make it unique to the contents.
                 * (Eric)  
            	//retrieve the unique number for l at the merge point succUnit
            	//if there is no such number yet, generate one
            	//then assign the number to l in the outMap
                Map<ValueIntegervalueToNumber = .get(succUnit);
                if(valueToNumber==null) {
                	valueToNumber = new HashMap<ValueInteger>();
                Integer number = valueToNumber.get(l);
                if(number==null) {
                	number = ++;
    protected void flowThrough(HashMap<Value,ObjectinUnit uHashMap<Value,Objectout) {
    	Stmt s = (Stmt)u;
        if (s instanceof DefinitionStmt) {
            DefinitionStmt ds = (DefinitionStmts;
            Value lhs = ds.getLeftOp();
            Value rhs = ds.getRightOp();
            if (rhs instanceof CastExpr) {
            	//un-box casted value
				CastExpr castExpr = (CastExprrhs;
            	rhs = castExpr.getOp();
            if ((lhs instanceof Local
            		|| (lhs instanceof FieldRef && this..contains(new EquivalentValue(lhs))))
            	&& lhs.getType() instanceof RefLikeType) {
                if (rhs instanceof Local) {
                	//local-assignment - must be aliased...
                } else if(rhs instanceof ThisRef) {
                	//ThisRef can never change; assign unique number
                } else if(rhs instanceof ParameterRef) {
                	//ParameterRef can never change; assign unique number
                } else {
                	//assign number for expression
        } else {
        	//which other kind of statement has def-boxes? hopefully none...
        	assert s.getDefBoxes().isEmpty();
    private Object numberOfRhs(Value rhs) {
   		EquivalentValue equivValue = new EquivalentValue(rhs);
   			rhs = equivValue;
        Integer num = .get(rhs);
        if(num==null) {
            num = ++;
        return num;
    public static int thisRefNumber() {
    	//unique number for ThisRef (must be <1)
		return 0;
    public static int parameterRefNumber(ParameterRef r) {
    	//unique number for ParameterRef[i] (must be <0)
		return -1 - r.getIndex();
	protected void copy(HashMap<Value,ObjectsourceMapHashMap<Value,ObjectdestMap)

Initial most conservative value: has to be org.omg.CORBA.UNKNOWN (top).
    protected HashMap<Value,ObjectentryInitialFlow()
    	HashMap<Value,Objectm = new HashMap<Value,Object>();
        for (Value l : (Collection<Value>) ) {
        return m;

Initial bottom value: objects have no definitions.
    protected HashMap<Value,ObjectnewInitialFlow()
    	HashMap<Value,Objectm = new HashMap<Value,Object>();
        for (Value l : (Collection<Value>) ) {
        return m;
Returns a string (natural number) representation of the instance key associated with l at statement s or null if there is no such key associated or UNKNOWN if the value of l at s is UNKNOWN.

l any local of the associated method
s the statement at which to check
    public String instanceKeyString(Local lStmt s) {
        Object ln = getFlowBefore(s).get(l);
        if(ln==null) {
        	return null;
        } else  if(ln==) {
        	return .toString();
        return ln.toString();
Returns true if this analysis has any information about local l at statement s (i.e. it is not UNKNOWN). In particular, it is safe to pass in locals/statements that are not even part of the right method. In those cases false will be returned. Permits s to be null, in which case false will be returned.
    public boolean hasInfoOn(Local lStmt s) {
    	HashMap<Value,ObjectflowBefore = getFlowBefore(s);
    	if(flowBefore==null) {
    		return false;
    	} else {
    		Object info = flowBefore.get(l);
    		return info!=null && info!=;

true if values of l1 (at s1) and l2 (at s2) have the exact same object IDs, i.e. at statement s1 the variable l1 must point to the same object as l2 at s2.
    public boolean mustAlias(Local l1Stmt s1Local l2Stmt s2) {
        Object l1n = getFlowBefore(s1).get(l1);
        Object l2n = getFlowBefore(s2).get(l2);
        if (l1n ==  || l2n == )
            return false;
        return l1n == l2n;
	protected void merge(HashMap<ValueObjectin1,
			HashMap<ValueObjectin2HashMap<ValueObjectout) {
		throw new UnsupportedOperationException("not implemented; use other merge method instead");
New to GrepCode? Check out our FAQ X