Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 2000 Feng Qian
   *
   * 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.annotation.arraycheck;
 import soot.options.*;
 
 import soot.*;
 import soot.jimple.*;
 import soot.util.*;
 
 import java.util.*;
 
 {
     HashSet<LocalfullSet = new HashSet<Local>();
 
     /* for each unit, kill set has variables to be killed.
      * gen set was considered with conditionOfGenSet,
      * for example, gen set of unit s are valid only when the condition object.
      * was in the living input set.
      */
 
     // s --> a kill all a[?].
     // s --> true
 
     IntContainer zero = new IntContainer(0);
 
     private final boolean fieldin;
 
     private final boolean arrayin;
 
     private final boolean csin;
 
     private final boolean rectarray;
 
                                       boolean takeFieldRef
                                       boolean takeArrayRef,
                                       boolean takeCSE,
                                       boolean takeRectArray)
     {
         super(dg);
         
          = takeFieldRef;
          = takeArrayRef;
          = takeCSE;
          = takeRectArray;
         
         if (Options.v().debug()) 
             G.v()..println("Enter ArrayIndexLivenessAnalysis");
         
          = (ExceptionalUnitGraph)dg;
         
         /* compute gen set, kill set, and condition set */
          = new HashMap<StmtHashSet<Object>>(.size()*2+1);
          = new HashMap<StmtHashSet<Value>>(.size()*2+1);
          = new HashMap<StmtHashSet<Value>>(.size()*2+1);
          = new HashMap<StmtHashSet<Value>>(.size()*2+1);
         
         if ()
        {
             = new HashMap<ObjectHashSet<Value>>();
             = new HashMap<ObjectHashSet<Value>>();
             = new HashSet<Value>();
        }
        
        if ()
        {
             = new HashMap();
             = new HashSet();
            
             = new HashMap<DefinitionStmtValue>();
             = new HashMap<DefinitionStmtBoolean>();
            
            if ()
            {
                 = new HashSet<Local>();
                retrieveMultiArrayLocals(.getBody(), );
            }
        }
        
        if ()
        {
             = new HashMap<ValueHashSet<Value>>();
        }
        getAllRelatedMaps(.getBody());
        doAnalysis();
        if (Options.v().debug()) 
            G.v()..println("Leave ArrayIndexLivenessAnalysis");
    }
    {
        return ;
    }
    {
        return ;
    }
    public HashSet<ValuegetAllFieldRefs()
    {
        return this.;
    }
    public HashMap getLocalToArrayRef()
    {
        return ;
    }
    public HashSet getAllArrayRefs()
    {
        return ;
    }
    {
        return ;
    }
    {
        return ;
    }
    private void getAllRelatedMaps(Body body)
    {
        Iterator unitIt = body.getUnits().iterator();
        while (unitIt.hasNext())
        {
            Stmt stmt = (Stmt)unitIt.next();
            
            if ()
            {
                if (stmt instanceof DefinitionStmt)
                {
                    Value rhs = ((DefinitionStmt)stmt).getRightOp();
                    if (rhs instanceof BinopExpr
                    {
                        Value op1 = ((BinopExpr)rhs).getOp1();
                        Value op2 = ((BinopExpr)rhs).getOp2();
                        
                        if (rhs instanceof AddExpr
                        {
                            // op1 + op2 --> a + b
                            if ((op1 instanceof Local) &&
                                (op2 instanceof Local)) 
                            {
                                HashSet<Valuerefs = .get(op1);
                                if (refs == null)
                                {
                                    refs = new HashSet<Value>();
                                    .put(op1refs);
                                }
                                refs.add(rhs);
                                
                                refs = .get(op2);
                                if (refs == null)
                                {
                                    refs = new HashSet<Value>();
                                    .put(op2refs);
                                }
                                refs.add(rhs);
                            }
                        }
                        // a * b, a * c, c * a
                        else if (rhs instanceof MulExpr)
                        {
                            HashSet<Valuerefs = .get(op1);
                            if (refs == null)
                            {
                                refs = new HashSet<Value>();
                                .put(op1refs);
                            }
                            refs.add(rhs);
                
                            refs = .get(op2);
                            if (refs == null)
                            {
                                refs = new HashSet<Value>();
                                .put(op2refs);
                            }
                            refs.add(rhs);
                        }
                        else if (rhs instanceof SubExpr)
                        {
                            if (op2 instanceof Local)
                            {
                                HashSet<Valuerefs = .get(op2);
                                if (refs == null)
                                {
                                    refs = new HashSet<Value>();
                                    .put(op2refs);
                                }
                                refs.add(rhs);
                                
                                if (op1 instanceof Local)
                                {
                                    refs = .get(op1);
                                    if (refs == null)
                                    {
                                        refs = new HashSet<Value>();
                                        .put(op1refs);
                                    }
                                    refs.add(rhs);
                                }
                            }
                        }
                    }
                }
            }
            
            List vboxes = stmt.getUseAndDefBoxes();
            Iterator vboxIt = vboxes.iterator();
            while (vboxIt.hasNext())
            {
                Value v = ((ValueBox)vboxIt.next()).getValue();
                
                if ()
                {
                    if (v instanceof InstanceFieldRef)
                    {
                        Value base = ((InstanceFieldRef)v).getBase();
                        SootField field = ((InstanceFieldRef)v).getField();
                        
                        HashSet<Valuebaseset = .get(base);
                        if (baseset == null)
                        {
                            baseset = new HashSet<Value>();
                            .put(basebaseset);
                        }
                        
                        baseset.add(v);
                        
                        HashSet<Valuefieldset = .get(field);
                        if (fieldset == null)
                        {
                            fieldset = new HashSet<Value>();
                            .put(fieldfieldset);
                        }
                        fieldset.add(v);
                    }
                    if (v instanceof FieldRef)
                        .add(v);
                }
                if ()
                {
                    // a = ...   --> kill all a[x] nodes.
                    // a[i] = .. --> kill all array references.
                    // m(a)      --> kill all array references 
                    // i = ...   --> kill all array reference with index as i
                /*
                if (v instanceof ArrayRef)
                {
                    Value base = ((ArrayRef)v).getBase();
                    Value index = ((ArrayRef)v).getIndex();
                    HashSet refset = (HashSet)localToArrayRef.get(base);
                    if (refset == null)
                    {
                        refset = new HashSet();
                        localToArrayRef.put(base, refset);
                    }
                    refset.add(v);
                    if (index instanceof Local)
                    {
                        refset = (HashSet)localToArrayRef.get(index);
                        if (refset == null)
                        {
                            refset = new HashSet();
                            localToArrayRef.put(index, refset);
                        }
                        refset.add(v);
                    }           
                    allArrayRefs.add(v);
                }
                */
                }
            }
        }
    }
    
    private void retrieveAllArrayLocals(Body bodySet<Localcontainer)
    {
        Chain locals = body.getLocals();
        Iterator localIt = locals.iterator();
        while (localIt.hasNext())
        {
            Local local = (Local)localIt.next();
            
            Type type = local.getType();
            
            if (type instanceof IntType
                || type instanceof ArrayType)
                container.add(local);
        }
    }
    
    private void retrieveMultiArrayLocals(Body bodySet<Localcontainer)
    {
        Chain locals = body.getLocals();
        
        Iterator localIt = locals.iterator();
        
        while (localIt.hasNext())
        {
            Local local = (Local)localIt.next();
            Type type = local.getType();
            
            if (type instanceof ArrayType)
            {
                if (((ArrayType)type). > 1)
                    this..add(local);
            }
        }
    }
    private void getGenAndKillSetForDefnStmt(DefinitionStmt asstmt
                                             HashMap<StmtHashSet<Value>> absgen,
                                             HashSet<Objectgenset,
                                             HashSet<Valueabsgenset,
                                             HashSet<Valuekillset,
                                             HashSet<Valuecondset)
    {
        /* kill left hand side */
        Value lhs = asstmt.getLeftOp();
        Value rhs = asstmt.getRightOp();
        
        boolean killarrayrelated = false;
        boolean killallarrayref = false;
        
        if ()
        {
            if (lhs instanceof Local)
            {
                HashSet related = .get(lhs);
                if (related != null)
                    killset.addAll(related);
            }
            else
                if (lhs instanceof StaticFieldRef)
                {
                    killset.add(lhs);
                    condset.add(lhs);
                }
                else
                    if (lhs instanceof InstanceFieldRef)
                    {
                        SootField field = ((InstanceFieldRef)lhs).getField();
                        HashSet related = .get(field);
                        if (related != null)
                            killset.addAll(related);
                        condset.add(lhs);
                    }
            
            if (asstmt.containsInvokeExpr())
            {
                /*
                Value expr = asstmt.getInvokeExpr();
                List parameters = ((InvokeExpr)expr).getArgs();
                // add the method invocation
                boolean killall = false;
                if (expr instanceof InstanceInvokeExpr)
                    killall = true;
                else
                {
                    for (int i=0; i<parameters.size(); i++)
                    {
                    Value para = (Value)parameters.get(i);
                    if (para.getType() instanceof RefType)
                    {
                        killall = true;
                        break;
                    }
                    }
                }
    
                if (killall)
                {
                    killset.addAll(allInstFieldRefs);
                }   
                */
                killset.addAll();
            } 
        }
        
        if ()
        {
            // a = ... or i = ...
            if (lhs instanceof Local)
            {
                killarrayrelated = true;
            }
            else
                // a[i] = ...
                if (lhs instanceof ArrayRef)
                {
                    killallarrayref = true;
                    condset.add(lhs);
                }
            
            // invokeexpr kills all array references.
            if (asstmt.containsInvokeExpr())
            {
                killallarrayref = true;
            }
        }
        
        if ()
        {
            HashSet exprs = .get(lhs);
            if (exprs != null)
                killset.addAll(exprs);
            if (rhs instanceof BinopExpr)
            {
                Value op1 = ((BinopExpr)rhs).getOp1();
                Value op2 = ((BinopExpr)rhs).getOp2();
                if (rhs instanceof AddExpr)
                {
                    if ((op1 instanceof Local) &&
                        (op2 instanceof Local))
                        genset.add(rhs);
                }
                else
                    if (rhs instanceof MulExpr)
                    {
                        if ((op1 instanceof Local) ||
                            (op2 instanceof Local))
                            genset.add(rhs);
                    }
                    else
                        if (rhs instanceof SubExpr)
                        {
                            if (op2 instanceof Local)
                                genset.add(rhs);
                        }
            }
        }
        
        if ((lhs instanceof Local)&&(.contains(lhs)))
        {
            killset.add(lhs);
            /* speculatively add lhs as live condition. */
            condset.add(lhs);
        }
        else if (lhs instanceof ArrayRef)
        {
            /* a[i] generate a and i. */
            Value base = ((ArrayRef)lhs).getBase();
            Value index = ((ArrayRef)lhs).getIndex();
            ArrayList genList = new ArrayList();
            
            absgenset.add(base);
            
            if (index instanceof Local)
            {
                absgenset.add(index);
            }
        }
        
        if (rhs instanceof Local)
        {
            /* only lhs=rhs is valid. */
            /*
              if (lhs instanceof Local && fullSet.contains(rhs))
              genset.add(rhs);
            */
            if (.contains(rhs))
                genset.add(rhs);
            
            /*
              if (fieldin && (lhs instanceof FieldRef))
              genset.add(rhs);
            */
        }
        else if (rhs instanceof FieldRef)
        {
            if ()
                genset.add(rhs);
        }
        else if (rhs instanceof ArrayRef)
        {
            /* lhs=a[i]. */
            Value base = ((ArrayRef)rhs).getBase();
            Value index = ((ArrayRef)rhs).getIndex();
            
            absgenset.add(base);
            if (index instanceof Local)
            {
                absgenset.add(index);
            }
            
            if ()
            {
                genset.add(rhs);
                if ()
                    genset.add(Array2ndDimensionSymbol.v(base));
            }
        }
        else if (rhs instanceof NewArrayExpr)
        {
            /* a = new A[i]; */
            Value size = ((NewArrayExpr)rhs).getSize();
            if (size instanceof Local)
                genset.add(size);
        }
        else if (rhs instanceof NewMultiArrayExpr)
        {
            /* a = new A[i][]...;*/
            /* More precisely, we should track other dimensions. */
                        
            List sizes = ((NewMultiArrayExpr)rhs).getSizes();
            Iterator sizeIt = sizes.iterator();
            while (sizeIt.hasNext())
            {
                Value size = (Value)sizeIt.next();
                
                if (size instanceof Local)
                    genset.add(size);
            }
        }
        else if (rhs instanceof LengthExpr)
        {
            /* lhs = lengthof rhs */
            Value op = ((LengthExpr)rhs).getOp();
            genset.add(op);
        }
        else if (rhs instanceof JAddExpr)                        
        {
            /* lhs = rhs+c, lhs=c+rhs */
            Value op1 = ((JAddExpr)rhs).getOp1();
            Value op2 = ((JAddExpr)rhs).getOp2();
            
            if ((op1 instanceof IntConstant) &&
                (op2 instanceof Local))
            {
                genset.add(op2);
            }
            else if ((op2 instanceof IntConstant) &&
                     (op1 instanceof Local))
            {
                genset.add(op1);
            }
        }
        else if (rhs instanceof JSubExpr)
        {
            Value op1 = ((JSubExpr)rhs).getOp1();
            Value op2 = ((JSubExpr)rhs).getOp2();
            
            if ((op1 instanceof Local) &&
                (op2 instanceof IntConstant))
            {
                genset.add(op1);
            }
        }
        
        if ()
        {
            if (killarrayrelated)
                .put(asstmtlhs);
            
            if (killallarrayref)
                .put(asstmtnew Boolean(true));
        }
    }
    private void getGenAndKillSet(Body bodyHashMap<StmtHashSet<Value>> absgenHashMap<StmtHashSet<Object>> genHashMap<StmtHashSet<Value>> killHashMap<StmtHashSet<Value>> condition)
    {
        Iterator unitIt = body.getUnits().iterator();
        while (unitIt.hasNext())
        {
            Stmt stmt = (Stmt)unitIt.next();
            HashSet<Objectgenset = new HashSet<Object>();
            HashSet<Valueabsgenset = new HashSet<Value>();
            HashSet<Valuekillset = new HashSet<Value>();
            HashSet<Valuecondset = new HashSet<Value>();
            
            if (stmt instanceof DefinitionStmt)
            {
                getGenAndKillSetForDefnStmt((DefinitionStmt)stmtabsgen,
                                            gensetabsgenset
                                            killsetcondset);
            }
            else if (stmt instanceof IfStmt)
            {
                /* if one of condition is living, than other one is live. */
                Value cmpcond = ((IfStmt)stmt).getCondition();
                
                if (cmpcond instanceof ConditionExpr)
                {
                    Value op1 = ((ConditionExpr)cmpcond).getOp1();
                    Value op2 = ((ConditionExpr)cmpcond).getOp2();
                    
                    if (.contains(op1) && .contains(op2))
                    {
                        condset.add(op1);
                        condset.add(op2);
                        
                        genset.add(op1);
                        genset.add(op2);
                    }
                }
            }
            
            if (genset.size() != 0)
                gen.put(stmtgenset);
            if (absgenset.size() != 0)
                absgen.put(stmtabsgenset);
            if (killset.size() != 0)
                kill.put(stmtkillset);
            if (condset.size() != 0)
                condition.put(stmtcondset);
        }
    }
    /* It is unsafe for normal units. */
    /* Since the initial value is safe, empty set. 
       we do not need to do it again. */
    protected Object newInitialFlow()
    {
        return new HashSet();
    }
    /* It is safe for end units. */
    protected Object entryInitialFlow()
    {
        return new HashSet();
    }
    protected void flowThrough(Object inValueObject unitObject outValue)
    {
        HashSet inset = (HashSet)inValue;
        HashSet outset = (HashSet)outValue;
        Stmt stmt = (Stmt)unit;
        
        /* copy in set to out set. */
        outset.clear();
        outset.addAll(inset);
        
        HashSet genset = .get(unit);
        HashSet absgenset = .get(unit);
        HashSet killset = .get(unit);
        HashSet condset = .get(unit);
        
        if (killset != null)
            outset.removeAll(killset);
        
        if ()
        {
            Boolean killall = .get(stmt);
            
            if ((killall != null) && killall.booleanValue())
            {
                List keylist = new ArrayList(outset);
                Iterator keyIt = keylist.iterator();
                while (keyIt.hasNext())
                {
                    Object key = keyIt.next();
                    if (key instanceof ArrayRef)
                        outset.remove(key);
                }
            }
            else
            {
                Object local = .get(stmt);
                if (local != null)
                {
                    List keylist = new ArrayList(outset);
                    Iterator keyIt = keylist.iterator();
                    while (keyIt.hasNext())
                    {
                        Object key = keyIt.next();
                        if (key instanceof ArrayRef)
                        {
                            Value base = ((ArrayRef)key).getBase();
                            Value index = ((ArrayRef)key).getIndex();
                            
                            if (base.equals(local) || index.equals(local))
                                outset.remove(key);
                        }
                        
                        if ()
                        {
                            if (key instanceof Array2ndDimensionSymbol)
                            {
                                Object base = ((Array2ndDimensionSymbol)key).getVar();
                                if (base.equals(local))
                                    outset.remove(key);
                            }
                        }
                    }
                }
            }
        }
        
        if (genset != null)
        {
            if (condset == null || (condset.size()==0))
                outset.addAll(genset);
            else
            {
                Iterator condIt = condset.iterator();
                while (condIt.hasNext())
                {
                    if (inset.contains(condIt.next()))
                    {
                        outset.addAll(genset);
                        break;
                    }
                }
            }
        }
        
        if (absgenset != null)
            outset.addAll(absgenset);
    }
    
    protected void merge(Object in1Object in2Object out)
    {
        HashSet inset1 = (HashSet)in1;
        HashSet inset2 = (HashSet)in2;
        HashSet outset = (HashSet)out;
        
        HashSet src = inset1;
        
        if (outset == inset1)
            src = inset2;
        else if (outset == inset2)
            src = inset1;
        else
        {
            outset.clear();
            outset.addAll(inset2);
        }
        
        outset.addAll(src);
    }
    
    protected void copy(Object sourceObject dest)
    {
        if (source == dest)
            return;
        
        HashSet sourceSet = (HashSet)source;
        HashSet destSet = (HashSet)dest;
        
        destSet.clear();
        destSet.addAll(sourceSet);
    }
New to GrepCode? Check out our FAQ X