Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 2000 Patrick Lam
   *
   * 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
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * 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.
  */
 
 /*
  * Modified by the Sable Research Group and others 1997-1999.  
  * See the 'credits' file distributed with Soot for the complete list of
  * contributors.  (Soot is distributed at http://www.sable.mcgill.ca/soot)
  */
 
 
 package soot.jimple.toolkits.scalar;
 import soot.*;
 import soot.jimple.*;
 
 import java.util.*;
 import soot.util.*;
 
 // future work: fieldrefs.
 
Implements an available expressions analysis on local variables. The current implementation is slow but correct. A better implementation would use an implicit universe and the kill rule would be computed on-the-fly for each statement.
 
 {
     private final HashMap<ValueEquivalentValuevalueToEquivValue;
 
     FlowSet emptySet;
     
     {
         super(dg);
 
         UnitGraph g = (UnitGraph)dg;
 
         /* we need a universe of all of the expressions. */
         Iterator unitsIt = g.getBody().getUnits().iterator();
         ArrayList<Valueexprs = new ArrayList<Value>();
 
         // Consider "a + b".  containingExprs maps a and b (object equality) both to "a + b" (equivalence).
         HashMap<EquivalentValueChaincontainingExprs = new HashMap<EquivalentValueChain>();
 
         // maps a Value to its EquivalentValue.
          = new HashMap<ValueEquivalentValue>();
 
         // maps an rhs to its containing stmt.  object equality in rhs.
          = new HashMap<ValueStmt>();
 
         HashMap<EquivalentValueChainequivValToSiblingList = new HashMap<EquivalentValueChain>();
 
         // Create the set of all expressions, and a map from values to their containing expressions.
         while (unitsIt.hasNext())
         {
             Stmt s = (Stmt)unitsIt.next();
 
             if (s instanceof AssignStmt)
             {
                 Value v = ((AssignStmt)s).getRightOp();
                 .put(vs);
                 EquivalentValue ev = .get(v);
                 if (ev == null)
                 {
                     ev = new EquivalentValue(v);
                     .put(vev);
                 }
 
                 Chain sibList = null;
                 if (equivValToSiblingList.get(ev) == null)
                     { sibList = new HashChain(); equivValToSiblingList.put(evsibList); }
                 else
                     sibList = equivValToSiblingList.get(ev);
                 
                 if (!sibList.contains(v)) sibList.add(v);
 
                 if (!(v instanceof Expr))
                     continue;
 
                 if (!exprs.contains(v))
                {
                    exprs.add(v);
                    // Add map values for contained objects.
                    Iterator it = v.getUseBoxes().iterator();
                    while (it.hasNext())
                    {
                        Value o = ((ValueBox)it.next()).getValue();
                        EquivalentValue eo = .get(o);
                        if (eo == null)
                        {
                            eo = new EquivalentValue(o);
                            .put(oeo);
                        }
                        if (equivValToSiblingList.get(eo) == null)
                            { sibList = new HashChain(); equivValToSiblingList.put(eosibList); }
                        else
                            sibList = equivValToSiblingList.get(eo);
                        if (!sibList.contains(o)) sibList.add(o);
                        Chain l = null;
                        if (containingExprs.containsKey(eo))
                            l = containingExprs.get(eo);
                        else
                        {
                            l = new HashChain();
                            containingExprs.put(eol);
                        }
                        if (!l.contains(ev))
                            l.add(ev);
                    }
                }
            }
        }
        FlowUniverse exprUniv = new ArrayFlowUniverse(exprs.toArray());
         = new ArrayPackedSet(exprUniv);
        // Create preserve sets.
        {
             = new HashMap<UnitBoundedFlowSet>(g.size() * 2 + 1, 0.7f);
            Iterator unitIt = g.iterator();
            while(unitIt.hasNext())
            {
                BoundedFlowSet killSet = new ArrayPackedSet(exprUniv);
                Unit s = (UnitunitIt.next();
                // We need to do more!  In particular handle invokeExprs, etc.
                // For each def (say of x), kill the set of exprs containing x.
                Iterator boxIt = s.getDefBoxes().iterator();
                while(boxIt.hasNext())
                {
                    ValueBox box = (ValueBoxboxIt.next();
                    Value v = box.getValue();
                    EquivalentValue ev = .get(v);
                    HashChain c = (HashChain)containingExprs.get(ev);
                    if (c != null)
                    {
                        Iterator it = c.iterator();
                        while (it.hasNext())
                        {
                            // Add all siblings of it.next().
                            EquivalentValue container = (EquivalentValue)it.next();
                            Iterator sibListIt = equivValToSiblingList.get(container).iterator();
                            while (sibListIt.hasNext())
                                killSet.add(sibListIt.next(), killSet);
                        }
                    }
                }
                // Store complement
                    killSet.complement(killSet);
                    .put(skillSet);
            }
        }
        // Create generate sets
        {
             = new HashMap<UnitBoundedFlowSet>(g.size() * 2 + 1, 0.7f);
            Iterator unitIt = g.iterator();
            while(unitIt.hasNext())
            {
                Unit s = (UnitunitIt.next();
                BoundedFlowSet genSet = new ArrayPackedSet(exprUniv);
                // In Jimple, expressions only occur as the RHS of an AssignStmt.
                if (s instanceof AssignStmt)
                {
                    AssignStmt as = (AssignStmt)s;
                    if (as.getRightOp() instanceof Expr)
                    {
                        // canonical rep of as.getRightOp();
                        Value gen = as.getRightOp();
                        boolean cantAdd = false;
                        if (gen instanceof NewExpr || 
                               gen instanceof NewArrayExpr || 
                               gen instanceof NewMultiArrayExpr)
                            cantAdd = true;
                        if (gen instanceof InvokeExpr)
                            cantAdd = true;
                        // Whee, double negative!
                        if (!cantAdd)
                            genSet.add(gengenSet);
                    }
                }
                // remove the kill set
                genSet.intersection(.get(s), genSet);
                .put(sgenSet);
            }
        }
        doAnalysis();
    }
    protected Object newInitialFlow()
    {
        BoundedFlowSet out = (BoundedFlowSet).clone();
        out.complement(out);
        return out;
    }
    protected Object entryInitialFlow()
    {
        return .clone();
    }
    protected void flowThrough(Object inValueObject unitObject outValue)
    {
        FlowSet in = (FlowSetinValueout = (FlowSetoutValue;
        // Perform kill
            in.intersection(.get(unit), out);
        // Perform generation
            out.union(.get(unit), out);
    }
    protected void merge(Object in1Object in2Object out)
    {
        FlowSet inSet1 = (FlowSetin1,
            inSet2 = (FlowSetin2;
        FlowSet outSet = (FlowSetout;
        inSet1.intersection(inSet2outSet);
    }
    
    protected void copy(Object sourceObject dest)
    {
        FlowSet sourceSet = (FlowSetsource,
            destSet = (FlowSetdest;
            
        sourceSet.copy(destSet);
    }
New to GrepCode? Check out our FAQ X